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

思路:
用动态规划的思路来做。用f[i]表示以s[i]结尾的括号匹配字符串,属性是最大值。从第二个字符开始检查,如果当前字符为 )或 ] ,以及距离上一个匹配好的字符串前的一个字符与其相匹配,则更新长度为f[i] = f[i - 1] + 2,同时可以检查前两个字符,如果为 )或者 ] 说明以那个字符结尾的字符串可以与当前的字符串相连。因为如果可以匹配为字符串则会将结果存在f[i] 中,所以实际上不需要匹配,只需要加上 f[i - f[i - 1] - 2] 即可。最后每次更新下最长的字符串长度和下标,因为要输出第一个最长的,所以只有在严格大于时才更新,最后根据长度和下标从原字符串中构造出答案输出即可。

代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. using namespace std;
  6. const int N = 1e6 + 10;
  7. int f[N];
  8. char str[N];
  9. int main()
  10. {
  11. scanf("%s", str + 1);
  12. cout << str;
  13. int len = strlen(str + 1);
  14. int mlen = 0, id = 0;
  15. for (int i = 2; i <= len; i ++)
  16. {
  17. if (str[i - f[i - 1] -1] == '(' && str[i] == ')' || str[i - f[i - 1] - 1] == '[' && str[i] == ']')
  18. {
  19. f[i] = f[i - 1] + f[i - f[i - 1] - 2] + 2;
  20. if (f[i] > mlen)
  21. {
  22. mlen = f[i];
  23. id = i;
  24. }
  25. }
  26. }
  27. for (int i = id - mlen + 1; i <= id; i++)
  28. {
  29. cout << str[i];
  30. }
  31. return 0;
  32. }

什么是树形 DP?

树形 DP(Dynamic Programming on Trees)是一种在 树结构 上使用 动态规划 解决问题的方法。它的核心思想是 自底向上 递归计算,每个节点的状态依赖于它的子节点的计算结果。

如果你熟悉普通的 动态规划(DP),你可以把树形 DP 理解为:

  • 普通 DP 在一维或二维数组上进行(如最长子序列、背包问题)。
  • 树形 DP 在树的节点之间进行(如子树计算、路径问题)。

树形 DP 的应用场景

树形 DP 主要用于 涉及树结构的最优决策问题,常见的题目类型包括:

1. 树的最小覆盖问题

题目: 选最少的节点,使得树中的所有边至少有一个端点被选。 解法: 定义 dp[u][0] 表示 u 不选,dp[u][1] 表示 u 选,递归计算。

2. 树的最大权路径和

题目: 给定一棵树,每条边上有权重,求从某个节点出发的最长路径。 解法: dp[u] 代表以 u 为根的子树的最长路径,递归求解。

3. 树的直径(最长路径)

题目: 求一棵树中两点之间的最长路径。 解法: 两次 DFS 或树形 DP 计算最长路径。

4. 树的最小删除代价

题目: 删除最少的节点,使得树变成某种结构(如二叉树)。 解法: dp[u] 表示删掉 u 的最小代价。

5. 祖先/子孙信息计算

题目: 计算树上每个节点的子孙数量、深度等信息。 解法: dp[u] 递归计算 u 的子树大小。


树形 DP 的基本步骤

  1. 建树(用邻接表存储)。
  2. 定义 DP 状态(每个节点可能有多种状态,如放置与不放置士兵)。
  3. 递归计算 DP(从叶子节点开始往上计算)。
  4. 返回根节点的最优解(一般是 min(dp[root][0], dp[root][1]))。

总结

树形 DP 是在树上进行的动态规划,通常用于计算子树信息、自底向上的最优决策,在树的路径问题、覆盖问题、删除问题、优化问题等场景中非常常见。它的核心是 递归计算每个节点的状态,并将结果传递给父节点

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

tag:
NOIP2009 提高组,搜索,剪枝,位运算,NOIP提高组,2009

思路:

  1. 核心变量解析
  • a[10][10]:存储数独棋盘,ai表示第i行第j格的数字(0表示空格)
  • r[10]:行约束,r[i]的二进制第k位表示第i行能否填数字k+1(1表示可用)
  • c[10]:列约束,c[j]的二进制第k位表示第j列能否填数字k+1
  • e[5][5]:九宫格约束,ex的二进制第k位表示第x行第y列九宫格能否填k+1
  • p[1<<11]:位掩码到数字的映射,p[1<<k]=k+1(快速获取候选数字)
  • o[1<<10]:预计算二进制中1的个数,o[mask]表示mask的候选数字个数
  • ans:存储最终的最大得分
  1. 关键函数解析
  • gs():根据位置计算得分,边缘得分低,中心得分高(计算公式:值*(6+距边缘距离))
  • init():初始化约束为全可用状态,预处理o[]和p[]的映射关系
  • dfs():采用最小候选数优先的回溯算法,通过位运算快速枚举候选值
  1. 算法流程
  • 预处理所有约束条件
  • 优先选择候选数最少的格子进行填充(剪枝优化)
  • 用位运算快速遍历所有候选数字
  • 递归搜索时动态更新约束条件
  • 达到填满状态时更新最大得分
  1. 位运算优化点
  • 用异或操作快速增删约束条件(r[i]^=mask)
  • 用lowbit技巧遍历候选数字(t&-t获取最低位的1)
  • 预计算o[]避免重复计算候选数个数

参考: https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路,爱了爱了。

代码:

  1. #include <iostream>
  2. using namespace std;
  3. int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
  4. int o[1 << 10];
  5. int gs(int i, int j)
  6. {
  7. return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
  8. }
  9. void init()
  10. {
  11. for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
  12. for (int i = 0; i < (1 << 9); i ++)
  13. {
  14. int t = i;
  15. while (t)
  16. {
  17. t &= t -1;
  18. o[i] ++;
  19. }
  20. }
  21. for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
  22. }
  23. void dfs(int cnt, int sum)
  24. {
  25. if (cnt == 0)
  26. {
  27. ans = max(ans, sum);
  28. }
  29. int mi = 10, x, y;
  30. for (int i = 0; i< 9; i++)
  31. for (int j = 0; j < 9; j ++)
  32. {
  33. if (!a[i][j])
  34. {
  35. int t = r[i] & c[j] & e[i / 3][j / 3];
  36. if (o[t] < mi)
  37. {
  38. mi = o[t], x = i, y = j;
  39. }
  40. }
  41. }
  42. int t = r[x] & c[y] & e[x / 3][y / 3];
  43. while (t)
  44. {
  45. int l = (t & -t);
  46. t -= l;
  47. a[x][y] = p[l];
  48. r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
  49. dfs(cnt -1, sum + gs(x, y));
  50. a[x][y] = 0;
  51. r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
  52. }
  53. }
  54. int main()
  55. {
  56. init();
  57. int cnt = 0, sum = 0;
  58. for (int i = 0; i < 9; i++)
  59. for (int j = 0; j < 9; j ++)
  60. {
  61. cin >> a[i][j];
  62. if (a[i][j])
  63. {
  64. r[i] -= 1 << a[i][j] - 1;
  65. c[j] -= 1 << a[i][j] - 1;
  66. e[i / 3][j / 3] -= 1 << a[i][j] -1;
  67. sum += gs(i, j);
  68. }else cnt ++;
  69. }
  70. dfs(cnt, sum);
  71. cout << ans << endl;
  72. return 0;
  73. }

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

tag:
SCOI2008,动态规划,搜索,记忆化搜索

思路:
开一个6维的数组来表示状态(因为每种情况有多种,所以不能用压位bit),分别表示足够涂1, 2, 3, 4, 5块木头的颜色有几种,最后一维表示上一种颜色的种类。然后用记忆化搜索来做。参考: https://www.luogu.com.cn/article/fhusu9wq

代码:

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. typedef long long ll;
  5. ll MOD = 1e9 + 7;
  6. int n, t[6];
  7. ll dp[16][16][16][16][16][6];
  8. ll dfs(int a, int b, int c, int d, int e, int last)
  9. {
  10. if (dp[a][b][c][d][e][last] != -1) return dp[a][b][c][d][e][last];
  11. if (a + b + c + d + e == 0) return 1;
  12. ll res = 0;
  13. if (a) res += (a - (last == 2)) * dfs(a - 1, b, c, d, e, 1);
  14. if (b) res += (b - (last == 3)) * dfs(a + 1, b - 1, c, d, e, 2);
  15. if (c) res += (c - (last == 4)) * dfs(a, b + 1, c - 1, d, e, 3);
  16. if (d) res += (d - (last == 5)) * dfs(a, b, c + 1, d - 1, e, 4);
  17. if (e) res += e * dfs(a, b, c, d + 1, e - 1, 5);
  18. dp[a][b][c][d][e][last] = res % MOD;
  19. return dp[a][b][c][d][e][last];
  20. }
  21. int main()
  22. {
  23. cin >> n;
  24. for (int i = 0; i < n; i ++)
  25. {
  26. int a;
  27. cin >> a;
  28. t[a] ++;
  29. }
  30. memset(dp, -1, sizeof dp);
  31. ll ans = dfs(t[1], t[2], t[3], t[4], t[5], 0);
  32. cout << ans << endl;
  33. return 0;
  34. }