AT_DP

攻略

1. 先设计一个一定保证正确性的状态，可以完全朴素甚至可以n维

2. 考虑保证正确性的情况下：合并同类状态，消除无用状态，消除无用转移。

3. 对递推式进行分类，只与当前点有关的直接处理，只与以前相关的点预处理，既与当前有关又与现在有关考虑斜率优化（有单调性用单调队列，否则二分或李超）

A

显然

B

显然

C

显然

D

01背包模板
设 \(dp[i][j]\) 表示考虑了 $i $ 个物品，背包容量为 $ j $ 的最大价值

• 选第 $ i $ 件物品，那么背包容量剩余 $ j−w_i ，i−1 $ 个物品，价值为 $ dp[i−1][j−w_i]+v_i$
• 不选第 $ i $ 件物品，那么背包容量仍然不变为 $ j $ ，这时价值为 $ dp[i−1][j] $

所以可以得到 $ dp $ 的转移方程:

$$ dp[i][j]=max(dp[i−1][j−w_i]+v_i,dp[i−1][j])$$

滚动数组状态变为 $ dp[j] $ ,倒序枚举

则原方程变为：

$$ dp[j]=max⁡(dp[j−w_i]+v_i,dp[j]) $$

E

设 $ dp[i][j] $ 表示考虑 $ i $ 个物品,总价值是 $ j $ 所需的最小容量

• 拿第 $ i $ 件物品,那么别的物品的总价值需要凑出 $ j−v_i $ 考虑 $ i−1 $ 件物品的最优选取方式,即最终重量为 $ dp[i−1][j−v_i]+w_i $ 。

• 不拿第 $ i $ 件物品，那么别的物品需要凑出 $ j $ 的价值。考虑前 $ i−1 $ 件物品的最优选取方式，即最小重量为 $ dp[i−1][j] $

所以可以得到 $ dp $ 的转移方程:

$$dp[i][j]=min(dp[i−1][j−v_i]+w_i,dp[i−1][j])$$

滚动数组

则原方程变为：

$$ dp[j]=min(dp[j−v_i]+w_i,dp[j])$$

F

设状态 $ dp[i][j] $ 为 $ s $ 的前 $ i $ 项与 $ t $ 的前 $ j $ 项的 LCS

• 如果 $ s[i]=t[j] $ ，则 $ dp[i][j]=dp[i−1][j−1]+1 $

• 否则， $ dp[i][j]=max (⁡ dp[i−1][j],dp[i][j−1] )$

同时记录路径，最后从 $ (n,m) $ 向前回溯得到字符串

G

由于该题为有向无环图，因此我们可以按序去搜索遍历每一个点。若该点未被访问过，则对其进行搜索；否则，就可以直接对该点保存的答案进行求最大。

H

显然

I

设 $ dp[i][j] $ 表示前 $ i $ 个元素有 $ j $ 个向上的概率。只需要枚举当前硬币是向上还是向下即可，与背包类似。

转移方程为：

$$ f[i][j]=f[i−1][j−1]×pi+f[i−1][j]×(1−pi) $$

计算完毕后，统计一半硬币向上的答案。

J

考虑最暴力的做法，用 $ dp[a_1][a_2] ... [a_n] $ 表示第 $ i $ 盘还剩 $ a_i $个寿司的期望次数。那么枚举随机到的数 $ i $ 就可以得到方程：

$$ dp[a1][a2]⋅⋅⋅[an]=1+\sum _{i=1}^{n} \frac{1}{n} dp[a1][a2]...[max⁡(a_i−1,0)]...[an] $$

注意到第几盘寿司没有区别，因此可以合并状态，只记录剩余寿司的盘数
因为 $ ai≤3 $ 所以至多有四种不同数值： $ 0,1,2,3$ 。我们重新定义状态 $ dp[a][b][c][d] $ 表示当前还剩下 $ a/b/c/d $ 盘有 $ 0/1/2/3 $ 个寿司。
枚举当前随机到的盘子里还剩几只寿司得到如下方程：

$$dp[a][b][c][d]=1+\frac andp[a][b][c][d]+\frac bndp[a+1][b−1][c][d]+\frac cndp[a][b+1][c−1][d]+\frac dndp[a][b][c+1][d−1]$$

移项整理得到转移方程：

$$ dp[a][b][c][d]=\frac{b+c+d}n+\frac{b+c+d}b​dp[a+1][b−1][c] [d]+\frac{b+c+d}cdp[a][b+1][c−1][d]+\frac{b+c+d}ddp[a][b][c+1][d−1] $$

注意到 \(a+b+c+d=n\)
因此任意三个数可以确定另一个数，所以可以合并状态，又因为 \(a\) 在方程中参与度不高，所以把 \(a\) 这一维压掉。
得到

$$dp[b][c][d]=\frac{b+c+d}n​+\frac{b+c+d}b​dp[b−1][c][d]+\frac{b+c+d}c​dp[b+1][c−1][d]+\frac{b+c+d}d​dp[b][c+1][d−1]$$

K

设状态很重要，如果设某一个人的胜负，每一步状态都需要考虑两个决策，过于困难。

若设状态为当前操作者的胜负，则只需要考虑一个人的决策（其实是因为题面中两人没有本质上的的区别）

设 $ dp[i] $ 表示在剩余 $ i $ 块石头时，当前操作者的胜负。

显然，状态 $ dp[i] $ 可以转移到 $dpi+a_j $ 。

有一个显然的结论：在剩余 $ 0 $ 块石头时，当前操作者必败。

那么，如果一个状态能转移到一个必败状态，那么当前操作者一定必胜。

当前操作者只需要选择转移到那个使对手必败的状态，就可以让自己必胜(这也是博弈论的重要结论)。

所以我们可以从 $ dp[1] $ 开始递推求解，最终答案为 $ dp[k] $ 。

L

显然游戏过程中剩下的数必然是连续的一段。设 $ dp[i][j] $ 表示剩下下标为 $ [i,j] $ 的数时，先手（并非当前的先手而是开始时的先手，下同）能取得的最大分数差。

分两种情况讨论：

• 已经取走的数为偶数个，此时先手取， $ dp[i][j]=max⁡(dp[i+1][j]+a_i,dp[i][j−1]+a_j) $ 。

• 已经取走的数为奇数个，此时后手取， $ dp[i][j]=min⁡(dp[i+1][j]−a_i,dp[i][j−1]−a_j) $ 。

还有一种神奇的解法：

考虑数列中存在 $ 3 $ 个连续的数 $ a_i,a_{i+1},a_{i+2} $ 满足 $ a_i≤a_{i+1} $ 并且 $ a_{i+1}≥a_{i+2} $ ，此时一方任取两边的数，则另一方取中间的数最优，所以，这 $ 3 $ 个数可以等效合并为 $ 1 $ 个大小为 $ a_i+a_{i+2}−a_{i+1} $ 的数。

将数列中满足条件的数等效合并完后，数列一定满足先递减后递增，此时从两端贪心即可。

重点在于发现这种合并对全局生效

M

设 $ dp[i][j] $ 表示考虑到第 $ i $ 个小朋友，当前已经用掉 $ j $ 个糖的方案数。

转移方程：

$$dp[i][j]=\sum_{k=max(0,j-a_{i-1})}^jdp[i-1][k] $$

发现公式里每个 $ dp $ 值都由上一行中一段连续的 $ dp $ 值之和转移而来，可以前缀和优化转移。

N

设 $ dp[i][j] $ 为 $ i $ 到 $ j $ 的答案，
则枚举其中间点 $ k $ 取最小值：

合并的代价的最小值。

于是就可以推出转移方程：

$$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+\sum_{p=i}^{j}a_p )$$

前缀和优化