夏令营7.21总结

线性DP

难点：

• 如何划分阶段（看出他是线性DP）
• 如何定义子问题（需要什么状态）
• 哪些状态是需要考虑的（可行的），哪些又是不用考虑的
• 如何快速进行状态转移
• 如何减少状态数
• ……….

重点：

• 快速进行状态转移（主要）
• 减小状态数

T1 方格取数

f$[i][j]$表示从$(1,1)$到$(i,j)$的路上的数字和的最大值。

答案是$f[N][M]$。

正确的递推式：从$j=1$行的摸一个格子$(i’,j-1)$先向右一步到达$(i’,j)$，再向上或向下走到$(i,j)$。

T2 接龙

定义$f[i][j]$

• $f[i][j]$表示接龙到第i轮且第$i$轮的接龙序列以整数$j$结尾。

• $f[i][j]=-1$：没人

• $f[i][j]=0$：$\ge2$人

• $f[i][j]=k$：只有$k$这一个人可以接

T3 硬币问题

关于$f[i][j]$的递推式：

枚举第$i$种物品拿了几个。
$$
f[i][j]=max(f[i-1][j-p\times W_i]+a\times V_i)(0\le p\le min(C_i,j/W_i)
$$
注意到f[i][j]依赖$f[i-1][·]$的第二个下标两两都是差$W_i$的倍数，即这些下标模$W_i$都同余。

T4 翻转卡片2

T5 多重集合平均数

T6 Yet Another Knapsack Problem

子问题：$f[i][j][k]$：表示从前i种物品种选j个，总重量不超过k，求所选物品的总价的最大值

递推式：
$$
\begin{split}
f[0][j][k] &=
\begin{cases}
0 & \text{if } j = 0 \
-\infty & \text{other}
\end{cases} \
f[i][j][k] &= \max\limits_{0 \leq p \leq C_i} f[i - 1][j - p][k - i \cdot p] + p \cdot v_i \quad (1 \leq i \leq N)
\end{split}
$$
时间复杂度：$O(N^4)$

$\huge But$

即使使用滑动窗口优化，时间复杂度也有$O(N^3)$，过不了半点。

所以，我们还可以：$\huge 重新定义子问题$。

子问题：$g[i][j][k]$表示从$i$到$N$种物品中选择$j$个物品，总重量不超过$k$，所选物品的最大总价值。

递推式：
$$
\begin{split}
g[N + 1][j][k] &=
\begin{cases}
0 & \text{if } j = 0 \
-\infty & \text{otherwise}
\end{cases} \
g[i][j][k] &= \max\limits_{0 \leq p \leq C_i} g[i + 1][j - p][k - i \cdot p] + p \cdot v_i \quad (1 \leq i \leq N)
\end{split}
$$
这样，需要考虑的的状态就变少了。

T7 价值衰减的背包问题

子问题：$f[i][j]$代表了从前i种物品中选一些，所选物品的总重量不超过j，总满意度的最大值。递推式写不动了，太长了。