区间 dp 复习

今天做完了区间DP的复习, 简单写一下总结吧

石子合并 和 [USACO16OPEN]248 G 都是最直接的区间DP模板题, 注意到P3146使用bitset进行时空优化可以很大程度上降低代码复杂度.

关路灯 和 合唱队 则要在区间DP的过程中考虑到末状态为左右端点的情况, 由此不难发现该类题型的另一种变形, 即在DP时记录每一块的末状态与统一状态

[CQOI2007]涂色 和 CF607B Zuma 则要考虑到部分区间DP的后效性影响, 因此需要注意到一些特殊处理方法, 如上面两题均需考虑到左右端点状态相同时的特殊处理情况.

不过整体来讲这两天训练的题型还是偏简单, 在目前CSP/NOIP的形势下, 单论题目可能并不是很适合提高组的比赛, 但是就当巩固一下基础吧.

今天练的这几道区间DP题都是较为容易观察的$O(n^3)$DP, 所以其实类似问题更为重要的时关于特殊端点的判定问题.