资源描述:
《状态表示状态转移(进阶篇)》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
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