4根火柴拓补

1. 按状态类型分
写在前面：

从状态类型分，并不表示一题只从属于一类。其实一类只是一种状态的表示方法。可以好几种方法组合成一个状态，来解决问题。

1.1. 编号（长度）动态规划
共性总结

本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。

一般来说，有两种编号的状态：

状态(i)表示前i个元素决策组成的一个状态。

状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。

题库

a) 最长不下降子序列

以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。关于优化详见优化章。

一些问题可将数据有序化，转化成本题。

应用：

拦截导弹(NOIP99 Advance 1) 就是原题。

Beautiful People (sgu199)，要将数据有序化：其中一个权作为第一关键字不下降排列，另一个权作为第二关键字不上升。

Segment (ural 1078)，将线段的左端点有序化就可以了。

b) LCS

状态(i,j)，表示第1个字符串的第i位，与第2个字符串的第j位匹配，得到的最长的串。若有多个串要LCS，则加维，即几个串就几个维。我也将此题归入路径问题。

c) 花店橱窗布置(IOI99)

见路径问题。

1.2. 区间动态规划
共性总结

本类问题与下一章的划分问题的决策的分割点无序交集比较大（占本类问题的30%）。

题库