解题报告-论对“动态规划状态表示”的新理解

我们说动态规划状态表示的时候，一般认为它就是一句话，就表示完了，剩下的全部交给 \(dp\) 式子，推不出来再换一个状态表示。但是有些情况下，我们的状态表示是正确的，只是细节太多，在状态里写不完罢了。

看了这道题，发现题解里面都是状态表示漏了在 \(dp\) 公式里面修修补补的。这样修修补补的状态是永远修不完的，还不如看到一个漏的地方，直接回来重写状态表示，再从头开始理公式。

我现在用以上的方式把这道题理清楚：为什么这么做。

首先一个区间 \(dp\) 的状态表示：设 \(l,r\)。设 \(dp_{l,r}\) 表示区间 \([l,r]\) 的最大答案。然后一路往下推，发现了只能从子区间转移而来，没有加上任何的新东西，这样的情况肯定是漏了的，所以重来。

于是我们得到了第一个要点：当我们发现某个 \(dp\) 的转移跟题目条件毫无联系的时候，这个状态表示一定假了，所以重来。

想想漏掉了什么。首先，很明显，一个区间的问题 能从 子区间转移而来，这个是 对 的，但是 不完全。用类似于 \(\texttt{cdq}\) 分治的思想可以发现，答案就是左+中+右。很明显我们考虑漏了“中”，加上就对了。

于是我们得到了第二个要点：在我们状态表示的时候，一定要把状态划分为若干个集合，这样才能保证思路的清晰性。就算我们漏掉了什么，在表示集合的图上往上加就行了。这样写代码的时候，打一点看一眼草稿纸，就知道要从哪里转移，一个一个分块去做，思路清晰，代码也清晰。

综上所述，漏什么，加什么，不要在代码上直接加（修补），而是结合上漏的点在思路上重新考虑（重建）。结合昨天的，加也一定不要加重，防止不必要的去重。