区间 dp 复习

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

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

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

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

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

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




Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • 动手实现一个 RISC-V GPGPU(二):指令集设计
  • 数据结构 (CS1951@SJTU) 课程笔记汇总
  • 数据结构复健(四):树链剖分
  • 实现一个 std::map
  • 实现一个 std::priority_queue