(想来想去还是先弄DP计算几何就先放放) 1、背包模型包括0-1背包、无限背包、有限背包、有价值背包、小数背包(贪心即可)等,是极为经典的模型,其转化与优化也是很重要的。H P4^ k v3T V A 2、最长非降子序列模型 7i _ F+E N H g O8| | | s 改版:渡河问题、合唱队型等 3、最大子段和模型 改版:K大子段和、最佳游览,最大子矩阵和等。 4、LCS模型 ?:p0n E m$v |+r 改版:回文字串、多串的LCS等 5、括号序列模型 M Y3e V D:D 改版:关灯问题(TSOJ)、charexp(TSOJ)、最大算式等,核心思想在于以串的长度为阶段。 6、递推模型 p:l s#U i _1J L } 这类题是属于徘徊在DP与递归之间得一类题,本质是类似于记忆化搜索的一种填表,有很强的数学味。 &e n o A:l V 7、线段覆盖问题 改版:Tom的烦恼(TOJ)等。经常利用到离散化等技巧辅助。 ^'g R V1e+h&F 8、单词划分模型 和LCS基本上构成了字符串DP的主要类型。改版:奇怪的门(TOJ)等。 9、股票模型 8u F.[ x&m |8g!{ 这是DP优化的经典模型。改版有换外汇等。 ,o/z yw ?5\/d 10、连续段划分模型 即要求把数列划分成k个连续段,使每段和的最大值最小。改版有任务调度等。 x0e B6d k X j8t'v1| Y 11、游戏模型 这类题的阶段(一般是时间)和决策(一般就是游戏目标)很清楚,因此比较容易想到。改版:免费馅饼(NOI98)、Help Jimmy(CEOI2000)、瑰丽华尔兹(NOI2005,优化需要多费功夫)。 y KY/\ |
|