近期DP题目

几道DP题目

牛客练习赛 139C，25 武汉邀请赛 FG 等

C-大卫的密码（牛客练习赛139）

题意：给定一个 \(n\times m\) 的网格图，从 (s,1) 出发，每次可以向右或者向下移动，当光标移动到最后一行的某个格子时，继续向下移动则会到达 (1,i) 格子。需要移动光标到达 (t,m)，求最大价值和。

题解：二维 DP+限制。定义状态 \(dp[i][j]\) 表示在 (i,j) 位置时的最大价值和。因为纵向可以走到底然后从上面走下来，从左往右一列一列转移。

设 \(s_n=\sum_{i=1}^n a[i][j]\)，则转移方程为： \(dp_{i,j} \leftarrow \max_{k} \left( dp_{k,j-1} + \begin{cases} s_i - s_{k-1} & \text{if } ~k < i \\ s_n - (s_{k-1} - s_i) & \text{if } ~k > i \end{cases} \right)\)

DP 数组可以滚动优化。

P12593 沉石鱼惊旋

题意：有一张 n 个点 m 条边的简单无向带权连通图。进行 n 次操作，每次选择一个仍未被删除的点 u，删除点 u 和当前与 u 相连的所有边。总代价是这 n 次操作的代价和，求最小总代价。

题解：状压 DP。定义状态 \(f[S]\) 为已经删过点的集合为 S 时所能取得的最小代价。时间复杂度 \(O(2^n n^2)\)，可通过 n≤16 的范围。

P12597 穿睡衣军训

题意：给定两个字符串 s,t，求出一个字符串 x 满足：x 是 s 的子串、x 是 t 的子序列、长度最长、字典序最小。

题解：\(O(n^2)\) 枚举子串，判断子序列可以继承上一段的结果，优化到 \(O(Tn^2 \log m)\)。

2025武汉邀请赛-F 背包

题意：有 n 组物品，第 i 组有 \(a_i\) 个，每个重量为 \(2^{b_i}\)。m 个背包，每个承重为 k。求最小的 k 使所有物品都能放入。

2025武汉邀请赛-G 路径求和问题

题意：有一个 n×m 的网格，从 (1,1) 走到 (n,m)，只能往下或往右。一条路径的价值定义为路径上不同整数的数量。对于所有可能路径，求价值之和。

题解：使用组合计数 + 容斥。对于出现次数较少的数使用 func1（暴力 DP），出现次数较多的数使用 func2（整体容斥），块大小阈值取 \(\sqrt{nm}\)。