资源描述：
《状态表示状态转移(进阶篇)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、衢州一中胡承丰动态规划总结专题一状态表示在用动态规划解题时，我么往往第一个考虑的是数组维数，其实数组维度（和状态表示）是有规律可循的：A.二维空间的DP：一般采用二位数组——d[i，j]表示当i，j为某一边角时的极值（e：d[i，j]可以表示以i，j为右上角时所能构成的正方形的边长最大值——听不懂？接着往下看）。还有一种表示方法：d[i，num]表示走到第i各阶段的第num个位置：1234561234561，12，23，34，45，56，62，13，24，35，46，57，53，14，25，36，47，48，44，15，26，37，38，39，35，16，27，28，29，210，26，
2、17，18，19，110，111，1这种表示解决“多次访问同一图”类的DP题很有用。B.阶段决策类的DP：这里指阶段划分十分明显的题（0/1背包）。一般采用d[i,j]表示执行到第i各阶段，剩余代价为j时，所能取得的最高分。（如果限制条件多，可增加维度）。第-9-页共9页衢州一中胡承丰A.树形关系类的DP：一般用d[i]来表示以i为根节点的最优值，可以加维来保证正确性。B.线性关系类的DP：这一类的DP最简单，是每一个OIER的必备基础，在这里就不废话了。专题二状态转移（专题二与专题一的分类标准不同，因为dugushuiyi说这样分更好，感谢他）A.线性转移一般公式：d[i]=opera
3、tion（d[j]+w[j，i]）（w[i]为由j转移到i的消耗）{operation为求最值}B.阶段性转移一般公式：d[i，j]：=operation（d[i-1，k]+w[k，j]，d[i-2，……）如果只涉及到前面的有限个阶段，可以使用滚动数组。D[Imodn，j]=operation（d[(i-1)modn，k]+w[k，j]，d[(i-2)modn，……）C.树性转移一般公式：D[i，j]=max（d[lson[i]，k1]+w[j，k1]，d[rson[i]，k2]+w[j，k2]）遍历顺序一般为后序遍历顺序。第-9-页共9页衢州一中胡承丰A.多维空间转移一般公式：d[i，
4、j]:=max(d[i-1,j]+w1,d[i,j-1]+w2)复杂度分析：DP的复杂度为:状态表示的数组维数*状态转移的代价SoA的复杂度为O（n^2）BCD:O(n^3);专题三题目分类总结一、一般类试题题库：最长不下降子序列最长匹配前缀邮票组合共性总结：1、题目一般可以通过for语句来枚举状态，所以时间复杂度为O（N^2）本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。一般来说，有两种编号的状态：状态(i)表示前i个元素决策组成的一个状态。第-9-页共9页衢州一中胡承丰状态(i)表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。一、01背包：（
5、重点）★★★题库：01背包（USACO、vijos1025、1104）装箱问题（NOIP01Trade4）、取火柴问题(sgu153Playingwithmatches)共性总结：1、一般都从阶段的角度来表示状态2、因为d[i，j]只与d[i-1，k]有关，所以可以用滚动数组来实现。D[odd（i），j]各例分析：1、采药（NOIP2006、vijos）一个背包，每个物品只能放一次。(1)D[i，j]：=max（d[i，j]，d[i，j-t[i]]+p[i]）；D[I,j]表示决策了前i个物品，花费了j的代价优化：滚动数组.(2)D[odd（i），j]：=max（d[i-1，j]，d[o
6、dd（i-1），j-t[i]]+p[i]）；观察(2)不难发现，当我们算到j时，1àj-1并没有更新，而d[i-1，j-t[i]]一定在1àj-1的范围内，所以完全可以用一位数组，方程为：d[i]：=max（d[i]，d[i-t[j]]+p[j]）第-9-页共9页衢州一中胡承丰在最外层循环一下j就ok了。（精益求精）1、总分（USACO）一个背包，可以重复放物品。D[i]：=max（d[i]，d[i-t[j]]+p[j]）D[i]表示花费i各单位时间所能达到的最大值。（较简单）2、RaucousRockers（USACO）多个背包，不可以重复放物品，但放物品的顺序有限制。d[I,j,k]
7、:=max(d[I-1,j,k],d[I-1,j,k-t[i]]+p[i],d[i-1,j-1,maxtime-t[i]])d[I,j,k]表示决策到第i个物品、第j个背包，此背包花费了k的空间。d[I-1,j,k]表示不取i，d[I-1,j,k-t[i]]表示取了i病房入背包j中，d[i-1,j-1,maxtime-t[i]]表示取了i病房入背包j-1中。比较好理解。（本题也可以用滚动数组优化）3、FenceRails（USACO
