浅谈动态规划
0x01 一些想法
动态规划，是算法竞赛中非常常考的且极难突破的一个重难点，被神仙们分为了线性 dp、背包 dp、状态压缩等等。因为不同种类的 dp 都有相应的解法，并且相对应的题目还有不同的套路。这就导致 dp 的学习麻烦且复杂。那么，为什么不把所有的 dp 都看成一类题呢？（状态压缩过于特殊另说）？说句废话，所有的 dp 都是现设状态再想转移，最后再优化。那我们想想，这些状态是不是都有一个共同点？他利用这个数组的值或者说某一维去维护一些信息，但是出于维护的方式不太一样，我们才将他们分成了各种各样的 dp。那么好，我们为什么不玩花一点，把状态压缩姑且放到一类，暂且称他为 二进制下状态转移 dp，其他 dp 称为 十进制下状态转移 dp。这么分类的一个极大的好处就是，我们突破了传统的思想束缚，让你的思维更加简单，不是说上来就去想我到底要选哪种 dp，在这种事情上把自己的思维搞乱。而是挑战自己思维的极限，在维护的时候更加可以放开手脚。可能说到这里读者仍认为这是废话，但是当对这些有深刻理解的时候，自然会发现思想的一些转变。
0x02 这种思考过程
一般来说，当找到一个合适的状态后，显然就可以搞出来相应的转移。所以说，状态是最难的一步。在设状态时，先考虑我的每一维是否可以参与答案的存储或者是维护某一个位置等等等等，之后在考虑其所代表的值。虽然可能还是很废话，但我个人认为这要比把一堆 dp 放到一块要舒服得多，答题思路可能跟闫氏 dp 分析法很类似。所有的 dp 问题，本质上是有限集中的最值问题。这句话其实不太合适，应该改为所有的 dp 问题，本质上是有限集中的贪心问题。
0x03 一些题目
[SDOI2009] 学校食堂
第一步，判断是不是状态压缩。数据范围极小，定为状压。
之后考虑状态，设 \(f[i][j][k]\) 表示第 \(1\) 个人到第 \(i−1\) 个人已经打完饭，第 \(i\) 个人以及后面 \(7\) 个人是否打饭的状态为 \(j\)，当前最后一个打饭的人的编号为 \(i+k\)。
当第 \(i\) 个人已经打完饭了，则有 f[i + 1][j >> 1][k - 1] = min(f[i][j][k], f[i + 1][j >> 1][k - 1])。如果没打完，枚举八种情况，f[i][j ∣ (1 << h)][h] = min(f[i][j ∣ (1 << h)][h], f[i][j][k] + time(i + k, i + h))。然后这个题就结束了。
[ZJOI2013] 蚂蚁寻路
数据范围一眼知道不是状压（你看，这么分析只需要定是不是状压就行了，多省事儿）
令 f[i][j][p][h] 来表示前 i 行前 j 列，到第 p 个矩形，且第 p 个矩形高为 i - h + 1 时的最优解。g[i][j][p][h][0 / 1] 来表示高度比 i - h + 1 高的 / 矮的之中，f 数组中的最大值。
转移即为 \(f[i][j][p][h] = max(f[i][j-1][p][h],g[i][j-1][p-1][h][p \mod 2])+s[i][j]-s[h-1][j]\) 再分别考虑高峰和低谷就好了。
[JLOI2014] 天天酷跑
f[i][j][k] : 第 i 行 j 格高时, 已经连跳 k 次后的最优结果。
$f[i+1][j−1][k]=max(f[i+1][j−1][k],f[i][j][k]+cost[i+1][j−1]) $
\(f[i+h][j+h][k+1]=max(f[i][j][k]+\sum_{l=1}^{h}{cost[i+l][j+l][k]},f[i+h][j+h][k+1])\)
其中 cost[i][j] 表示该格的收益 \(h\) 表示跳跃高度。
[AHOI2016初中组] 黑白序列
f[i] : 变化字符串前 i 个字符中的问号, 能使字符串前 i 个字符组成一个黑白序列的方案数
然后缩左右边界更新答案即可。
[JSOI2016] 灯塔
f[i] 表示第 i 个灯塔要照亮前 i−1 座山的最小高度
\(f_i = max(f_i, h_{i - 1 - j^2} + j + 1)\)