NOI 一轮复习：状态设计

动态规划是 OI 最重要的部分之一。从学习与做题的角度来说，主要分为设计状态与优化两部分。其中前者更多的是做题和总结方法与套路，甚至需要一定的灵感；而后者相对吃经验。

值得注意的是，很多题目都要求我们在设计算法以前先将题目进行一定的转化，从而将一个不熟悉的模型转化为我们更容易把握的模型。这一点在动态规划的题目中体现的尤为明显。

在阅读本文之前，你应该对动态规划有基本的了解。

线性 DP

在线性结构上枚举每一维度进行转移的 DP。

较复杂，见原题面。

直接做怎么做？设 $f_{i,j,k}$ 表示前 $i$ 个数，当前前缀和为 $j$ ，最大前缀和为 $k$ ，然后枚举填什么刷表转移对于每个状态是 $O(1)$ 的，虽然能做，但是状态数炸了。

需要合并无效状态。同时记录前缀和和最大前缀和有些冗余，从这里入手。考虑对于一段后缀，如果它本身的最大前缀和是 $0$ ，那么它不会对前面的贡献产生影响，这时可以直接确定排除掉这段后缀的前缀的答案，也就是题目所求。

设 $f_{i,j}$ 代表考虑前 $i$ 个数，且满足 $[i+1,n]$ 的最大前缀和为 $j$ 的期望答案，答案是 $f_{i,0}$ 。那么转移：

如果 $j>0$ ，可以以 $p_i$ 的系数（第 $i+1$ 位填 $1$ ）转移到 $f_{i+1,j-1}$ ， $1-p_i$ 的系数（第 $i+1$ 位填 $-1$ ）转移到 $f_{i+1,j+1}$ 。
如果 $j=0$ ，那么第 $i+1$ 位一定是 $-1$ ，此时可以转移到 $f_{i+1,0}$ 和 $f_{i+1,1}$ 。

背包的变种很多，且都比较简单。基本模型：01 背包、完全背包、多重背包、分组背包、方案数背包的撤回（将转移的东西减去即可）。

一些杂项内容

只有 NOIP 难度。

设 $f_i$ 代表考虑前 $i$ 位的答案。只有 $lst_{a_i}$ 可以与 $a_i$ 匹配，如果要匹配，中间一大段都要染成同一个颜色，计算这一段有多少贡献，从 $f_{lst_{a_i} + 1}$ 转移过来。

记录前缀某一段的贡献即可快速计算任意一段有多少贡献。代码。