常用动态规划状态转移方程.doc-资料库

jsddj-2082798-常用DP状态转移方程.doc.pdf-第1页.png

第1页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第2页.png

第2页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第3页.png

第3页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第4页.png

第4页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第5页.png

第5页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第6页.png

第6页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第7页.png

第7页 / 共12页

jsddj-2082798-常用DP状态转移方程.doc.pdf-第8页.png

第8页 / 共12页

-我们将人生划为诡异的阶段·我们把这个世界表为丰富的状态 1. 资源问题 1 -----机器分配问题 F[I,j]:=max(f[i-1,k]+w[i,j-k]) 2. 资源问题 2 ------01 背包问题 F[I,j]:=max(f[i-1,j-v[i]]+w[i],f[i-1,j]); 3. 线性动态规划 1 -----朴素最长非降子序列 F[i]:=max{f[j]+1} 4. 剖分问题 1 -----石子合并 F[i,j]:=min(f[i,k]+f[k+1,j]+sum[i,j]); 5. 剖分问题 2 -----多边形剖分 F[I,j]:=min(f[i,k]+f[k,j]+a[k]*a[j]*a[i]); 6. 剖分问题 3 ------乘积最大 f[i,j]:=max(f[k,j-1]*mult[k,i]); 7. 资源问题 3 -----系统可靠性(完全背包) F[i,j]:=max{f[i-1,j-c[i]*k]*P[I,x]} 8. 贪心的动态规划 1 -----快餐问题 F[i,j,k]:=max{f[i-1,j',k']+(T[i]-(j-j')*p1-(k-k')*p2) div p3} 9. 贪心的动态规划 2 -----过河 f[i]=min{{f(i-k)} (not stone[i]) {f(i-k)}+1} (stone[i]); +贪心压缩状态 10. 剖分问题 4 -----多边形-讨论的动态规划 F[i,j]:=max{正正 f[I,k]*f[k+1,j]; 负负 g[I,k]*f[k+1,j]; 正负 g[I,k]*f[k+1,j];

负正 f[I,k]*g[k+1,j];} g 为 min 11. 树型动态规划 1 -----加分二叉树 (从两侧到根结点模型) F[I,j]:=max{f[I,k-1]*f[k+1,j]+c[k]} 12. 树型动态规划 2 -----选课 (多叉树转二叉树,自顶向下模型) F[I,j]表示以 i 为根节点选 j 门功课得到的最大学分 f[i,j]:=max{f[t[i].l,k]+f[t[i].r,j-k-1]+c[i]} 13. 计数问题 1 -----砝码称重 f[f[0]+1]=f[j]+k*w[j]; (1<=i<=n; 1<=j<=f[0]; 1<=k<=a[i];) 14. 递推天地 1 ------核电站问题 f[-1]:=1; f[i]:=2*f[i-1]-f[i-1-m] f[0]:=1; 15. 递推天地 2 ------数的划分 f[i,j]:=f[i-j,j]+f[i-1,j-1]; 16. 最大子矩阵 1 -----一最大 01 子矩阵 f[i,j]:=min(f[i-1,j],v[i,j-1],v[i-1,j-1])+1; ans:=maxvalue(f); 17. 判定性问题 1 -----能否被 4 整除 g[1,0]:=true; g[1,1]:=false; g[1,2]:=false; g[1,3]:=false; g[i,j]:=g[i-1,k] and ((k+a[i,p]) mod 4 = j) 18. 判定性问题 2 -----能否被 k 整除 f[I,j±n[i] mod k]:=f[i-1,j]; -k<=j<=k; 1<=i<=n 20. 线型动态规划 2 -----方块消除游戏 f[i,i-1,0]:=0 f[i,j,k]:=max{f[i,j-1,0]+sqr(len(j)+k), f[i,p,k+len[j]]+f[p+1,j-1,0]}

ans:=f[1,m,0] 21. 线型动态规划 3 -----最长公共子串，LCS 问题 f[i,j]={0 (i=0)&(j=0); f[i-1,j-1]+1 max{f[i,j-1]+f[i-1,j]}} (i>0,j>0,x[i]<>y[j]); (i>0,j>0,x[i]=y[j]); 22. 最大子矩阵 2 -----最大带权 01 子矩阵 O(n^2*m) 枚举行的起始，压缩进数列，求最大字段和，遇 0 则清零 23. 资源问题 4 -----装箱问题(判定性 01 背包) f[j]:=(f[j] or f[j-v[i]]); 24. 数字三角形 1 -----朴素の数字三角形 f[i,j]:=max(f[i+1,j]+a[I,j],f[i+1,j+1]+a[i,j]); 25. 数字三角形 2 -----晴天小猪历险记之 Hill 同一阶段上暴力动态规划 if[i,j]:=min(f[i,j-1],f[I,j+1],f[i-1,j],f[i-1,j-1])+a[i,j] 26. 双向动态规划 1 数字三角形 3 -----小胖办证 f[i,j]:=max(f[i-1,j]+a[i,j],f[i,j-1]+a[i,j],f[i,j+1]+a[i,j]) 27. 数字三角形 4 -----过河卒 //边界初始化 f[i,j]:=f[i-1,j]+f[i,j-1]; 28. 数字三角形 5 -----朴素的打砖块 f[i,j,k]:=max(f[i-1,j-k,p]+sum[i,k],f[i,j,k]); 29. 数字三角形 6 -----优化的打砖块 f[I,j,k]:=max{g[i-1,j-k,k-1]+sum[I,k]}

30. 线性动态规划 3 -----打鼹鼠’ f[i]:=f[j]+1;(abs(x[i]-x[j])+abs(y[i]-y[j])<=t[i]-t[j]) 31. 树形动态规划 3 ,[ if -----贪吃的九头龙 ]1,' ,[ lf j    ]0,' ,[ j lf   (&)1 ))1 j  ], kj min ],[ j id    ((1 i   0  ],1' ,[ k jrf j  ,[ ],' kj jrf   (( (&)0 i j or  ,[*]1,[ ]][ kd ipiw    ,[*]0,[ ]][ kd ipiw  ( )0 ))2 m      and 32. 状态压缩动态规划 1 -----炮兵阵地 Max(f[Q*(r+1)+k],g[j]+num[k]) If (map[i] and plan[k]=0) and ((plan[P] or plan[q]) and plan[k]=0) 33. 递推天地 3 -----情书抄写员 f[i]:=f[i-1]+k*f[i-2] 34. 递推天地 4 -----错位排列 f[i]:=(i-1)(f[i-2]+f[i-1]); f[n]:=n*f[n-1]+(-1)^(n-2); 35. 递推天地 5 -----直线分平面最大区域数 f[n]:=f[n-1]+n :=n*(n+1) div 2 + 1; 36. 递推天地 6 -----折线分平面最大区域数 f[n]:=(n-1)(2*n-1)+2*n; 37. 递推天地 7 -----封闭曲线分平面最大区域数 f[n]:=f[n-1]+2*(n-1) :=sqr(n)-n+2; 38 递推天地 8 -----凸多边形分三角形方法数 f[n]:=C(2*n-2,n-1) div n; 对于 k 边形

f[k]:=C(2*k-4,k-2) div (k-1); //(k>=3) 39 递推天地 9 -----Catalan 数列一般形式 1,1,2,5,14,42,132 f[n]:=C(2k,k) div (k+1); 40 递推天地 10 -----彩灯布置排列组合中的环形染色问题 f[n]:=f[n-1]*(m-2)+f[n-2]*(m-1); 41 线性动态规划 4 (f[1]:=m; f[2]:=m(m-1); -----找数线性扫描 sum:=f[i]+g[j]; (if sum=Aim then getout; if sum

48 资源问题 ------明明的预算方案：加花的动态规划 f[i,j]:=max(f[i,j],f[l,j-v[i]-v[fb[i]]-v[fa[i]]]+v[i]*p[i]+v[fb[i]]*p [fb[i]]+v[fa[i]]*p[fa[i]]); 49 资源问题 -----化工场装箱员 [ , , ]: min f n i  j         [ [ f n i getA n [ f n [ f n , 1,  [ , j i getA n 10  1, ], [ n i n i j getB n     1, ], 1, [ j getB n n n     ], , 10 1, [ j i getA n i j     i   n  ]] ]] j [ j getB n   1       1, n  10   i j ] 50 树形动态规划 -----聚会的快乐 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t[i]^.son,0]); f[i,0]:=sigma(f[t[i]^.son,3]); 51 树形动态规划 -----皇宫看守 f[i,2]:=max(f[i,0],f[i,1]); f[i,1]:=sigma(f[t[i]^.son,0]); f[i,0]:=sigma(f[t[i]^.son,3]); 52 递推天地 -----盒子与球 f[i,1]:=1; f[i,j]:=j*(f[i-1,j-1]+f[i-1,j]); 53 双重动态规划 -----有限的基因序列 f[i]:=min{f[j]+1} g[c,i,j]:=(g[a,i,j] and g[b,i,j]) or (g[c,i,j]) 54 最大子矩阵问题 -----居住空间 f[i,j,k]:=min(min(min(f[i-1,j,k],f[i,j-1,k]), min(f[i,j,k-1],f[i-1,j-1,k])), min(min(f[i-1,j,k-1],f[i,j-1,k-1]), f[i-1,j-1,k-1]))+1; 55 线性动态规划 ------日程安排 f[i]:=max{f[j]}+P[I]; (e[j]

56 递推天地 ------组合数 C[I,j]:=C[i-1,j]+C[I-1,j-1] C[I,0]:=1 57 树形动态规划 -----有向树 k 中值问题 F[I,r,k]:=max{max{f[l[i],I,j]+f[r[i],I,k-j-1]},f[f[l[i],r,j]+f[r[i],r, k-j]+w[I,r]]} 58 树形动态规划 -----CTSC 2001 选课 F[I,j]:=w[i](if i∈P)+f[l[i],k]+f[r[i],m-k](0≤k≤m)(if l[i]<>0) 59 线性动态规划 -----多重历史 f[i,j]:=sigma{f[i-k,j-1]}(if checked) 60 背包问题(+-1 背包问题+回溯) -----CEOI1998 Substract f[i,j]:=f[i-1,j-a[i]] or f[i-1,j+a[i]] 61 线性动态规划(字符串) -----NOI 2000 古城之谜 f[i,1,1]:=min{f[i+length(s),2,1], f[i+length(s),1,1]+1} f[i,1,2]:=min{f[i+length(s),1,2]+words[s],f[i+length(s),1,2]+w ords[s]} 62 线性动态规划 -----最少单词个数 f[i,j]:=max{f[I,j],f[u-1,j-1]+l} 63 线型动态规划 -----APIO2007 数据备份状态压缩＋剪掉每个阶段 j 前 j*2 个状态和 j*2+200 后的状态贪心动态规划 f[i]:=min(g[i-2]+s[i],f[i-1]); 64 树形动态规划 -----APIO2007 风铃 f[i]:=f[l]+f[r]+{1 (if c[l]d[r]) 0(d[l]=d[r]) g[l]=g[r]=1 then Halt; 65 地图动态规划

-----NOI 2005 adv19910 F[t,i,j]:=max{f[t-1,i-dx[d[[t]],j-dy[d[k]]]+1],f[t-1,i,j]; 66 地图动态规划 -----优化的 NOI 2005 adv19910 F[k,i,j]:=max{f[k-1,i,p]+1} j-b[k]<=p<=j; 67 目标动态规划 -----CEOI98 subtra F[I,j]:=f[I-1,j+a[i]] or f[i-1,j-a[i]] 68 目标动态规划 ----- Vijos 1037 搭建双塔问题 F[value,delta]:=g[value+a[i],delta+a[i]] or g[value,delta-a[i]] 69 树形动态规划 -----有线电视网 f[i,p]:=max(f[i,p],f[i,p-q]+f[j,q]-map[i,j]) leaves[i]>=p>=l, 1<=q<=p; 70 地图动态规划 -----vijos 某题 F[I,j]:=min(f[i-1,j-1],f[I,j-1],f[i-1,j]); 71 最大子矩阵问题 -----最大字段和问题 f[i]:=max(f[i-1]+b[i],b[i]); f[1]:=b[1] 72 最大子矩阵问题 -----最大子立方体问题枚举一组边 i 的起始，压缩进矩阵 B[I,j]+=a[x,I,j] 枚举另外一组边的其实，做最大子矩阵 73 括号序列 -----线型动态规划 f[I,j]:=min(f[I,j],f[i+1,j-1](s[i]s[j]=”()”or(”[]”)), f[I+1,j+1]+1 (s[j]=”(”or”[” ] , f[I,j-1]+1(s[j]=”)”or”]” ) 74 棋盘切割 -----线型动态规划 f[k,x1,y1,x2,y2]=min{min{f[k-1,x1,y1,a,y2]+s[a+1,y1,x2,y2], f[k-1,a+1,y1,x2,y2]+s[x1,y1,a,y2] min{}}

资料库

常用动态规划状态转移方程.doc

相关推荐

课程资源

热门标签

最新资料