昨天将一些没有用的可以卖的vps卖了。
今天将原来放在旧主机上的一个服务迁移到了现在的服务器上面。
racknerd上面的服务器我估计不好出,就到时候不续费就好。
现在相当于将每年的服务器成本降低了,太好了。

url: https://www.luogu.com.cn/problem/P1272

tag:
动态规划,树形DP

思路:
简单的树形DP和背包结合。令 f[u][j] 表示以u节点为根的子树在需要取出j个节点时最少需要断的边。最后在输出答案的时候在所有节点中选择一个答案最小的,注意选择其他节点为根节点时需要断去父节点和其之间的一条边。最后输出答案即可。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 200;
  7. int h[N], e[N * 2], ne[N * 2], idx;
  8. int s[N];
  9. int n, p;
  10. int f[N][N];
  11. void add(int a, int b)
  12. {
  13. e[idx] = b;
  14. ne[idx] = h[a];
  15. h[a] = idx ++;
  16. }
  17. void dfs(int u, int fa)
  18. {
  19. s[u] = 1;
  20. f[u][1] = 0;
  21. for (int i = h[u]; ~i; i = ne[i])
  22. {
  23. int v = e[i];
  24. if (v == fa) continue;
  25. dfs(v, u);
  26. s[u] += s[v];
  27. for (int j = min(s[u], p); j >= 0; j --)
  28. {
  29. f[u][j] += 1;
  30. for (int k = 0; k <= min(j, s[v]); k++)
  31. f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);
  32. }
  33. }
  34. }
  35. int main()
  36. {
  37. memset(h, -1, sizeof h);
  38. memset(f, 0x3f, sizeof f);
  39. cin >> n >> p;
  40. for (int i = 0; i < n - 1; i ++)
  41. {
  42. int a, b;
  43. cin >> a >> b;
  44. add(a, b), add(b, a);
  45. }
  46. dfs(1, 0);
  47. int res = f[1][p];
  48. for (int i = 2; i <= n; i ++) res = min(res, f[i][p] + 1);
  49. cout << res << endl;
  50. return 0;
  51. }

url: https://www.luogu.com.cn/problem/P3177

tag:
动态规划,树形DP

思路:
f[u][j] 表示以u为根节点的子树中,恰好有j个黑点时的收益。之后就是和分组背包类似的思路,对于每一个相连的节点,由当那个节点取k个黑点时更新过来,在不同的k值之间取一个最大值。使用 (k * (m - k) + (s[v] - k) * (n - m - s[v] + k)) * w[i] 来计算u和v之间边对答案的贡献。最后记得开long long。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 2020;
  7. int h[N], e[N * 2], ne[N * 2], w[N * 2], idx;
  8. long long n, m;
  9. long long s[N];
  10. long long f[N][N];
  11. void add(int a, int b, int c)
  12. {
  13. e[idx] = b;
  14. w[idx] = c;
  15. ne[idx] = h[a];
  16. h[a] = idx ++;
  17. }
  18. void dfs(int u, int fa)
  19. {
  20. s[u] = 1;f[u][0] = f[u][1] = 0;
  21. for (int i = h[u]; ~i; i = ne[i])
  22. {
  23. int v = e[i];
  24. if (v == fa) continue;
  25. dfs(v, u);
  26. s[u] += s[v];
  27. for (int j = min(s[u], m); j >= 0; j --)
  28. for (int k = 0; k <= min((long long)j, s[v]); k ++)
  29. if (f[u][j - k] != -1)
  30. {
  31. long long val = (k * (m - k) + (s[v] - k) * (n - m - s[v] + k)) * w[i];
  32. f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] + val);
  33. }
  34. }
  35. }
  36. int main()
  37. {
  38. memset(h, -1, sizeof h);
  39. memset(f, -1, sizeof f);
  40. cin >> n >> m;
  41. for (int i = 0; i < n - 1; i ++)
  42. {
  43. int a, b, c;
  44. cin >> a >> b >> c;
  45. add(a, b, c), add(b, a, c);
  46. }
  47. dfs(1, 0);
  48. cout << f[1][m] << endl;
  49. return 0;
  50. }

url: https://www.luogu.com.cn/problem/P4170

tag:
字符串,动态规划,枚举,区间DP

思路:
使用 f[i][j] 表示从i到j这个区间中如果要涂到规定的情况,最少需要的涂色次数。因为有区间,所以可以使用区间DP,对于每一各区间ij来说如果第i个字符和第j个字符相同,则 f[i][j] 可以从 f[i][j - 1] 更新过来。如果不相同,则可以枚举这个区间中的每一个位置,将这个区间变为两个区间分别进行,由两个区间进行更新。初始状态,每个长度为1的区间,要达到规定的情况只需要涂一次就行。最后输出 f[0][n - 1] 即可。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 60;
  7. int f[N][N];
  8. int main()
  9. {
  10. char s[60];
  11. cin >> s;
  12. int n = strlen(s);
  13. for (int i = 0; i < n; i ++) f[i][i] = 1;
  14. for (int l = 1; l < n; l ++)
  15. {
  16. for (int i = 0; i + l < n; i++)
  17. {
  18. if (s[i] == s[i + l]) f[i][i + l] = f[i][i + l - 1];
  19. else
  20. {
  21. f[i][i + l] = f[i][i] + f[i + 1][i + l];
  22. for (int k = i + 1; k < i + l; k ++)
  23. f[i][i + l] = min(f[i][i + l], f[i][k] + f[k + 1][i + l]);
  24. }
  25. }
  26. }
  27. cout << f[0][n - 1] << endl;
  28. return 0;
  29. }

url: https://www.luogu.com.cn/problem/UVA1629

tag:
动态规划,枚举,前缀和

思路:
dp[lx][ly][rx][ry] 来记录某一个区间中,为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 30;
  7. int dp[N][N][N][N];
  8. int p[N][N];
  9. int cs;
  10. int pnum(int lx, int ly, int rx, int ry)
  11. {
  12. return p[rx][ry] - p[lx - 1][ry] - p[rx][ly - 1] + p[lx - 1][ly - 1];
  13. }
  14. int DP(int lx, int ly, int rx, int ry)
  15. {
  16. if (pnum(lx, ly, rx, ry) == 0) return 0x3f3f3f3f;
  17. if (pnum(lx, ly, rx, ry) == 1) return 0;
  18. int &d = dp[lx][ly][rx][ry];
  19. if (d != 0x3f3f3f3f) return d;
  20. for (int i = lx; i < rx; i ++)
  21. d = min(d, DP(lx, ly, i, ry) + DP(i + 1, ly, rx, ry) + ry - ly + 1);
  22. for (int i = ly; i < ry; i ++)
  23. d = min(d, DP(lx, ly, rx, i) + DP(lx, i + 1, rx, ry) + rx - lx + 1);
  24. return d;
  25. }
  26. int main()
  27. {
  28. int n, m, k;
  29. while(scanf("%d%d%d", &n, &m, &k) != EOF && n && m)
  30. {
  31. memset(p, 0, sizeof p);
  32. for (int i = 0; i < k; i ++)
  33. {
  34. int a, b;
  35. scanf("%d%d", &a, &b);
  36. p[a][b] = 1;
  37. }
  38. for (int i = 1; i <= n; i ++)
  39. for (int j = 1; j <= m; j ++)
  40. p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
  41. memset(dp, 0x3f, sizeof dp);
  42. printf("Case %d: %d\n", ++cs, DP(1, 1, n, m));
  43. }
  44. return 0;
  45. }