种DP方程.docVIP

100种dp方程 -段·我们把这个世界表为丰富的状态 ? 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]表示前i条生产线生产j个汉堡,k个薯条所能生产的最多饮料, ??? ??则最多套餐ans:=min{j?div?a,k?div?b,f[I,j,k]?div?c} ??F[i,j,k]:=max{f[i-1,j,k]+(T[i]-(j-j)*p1-(k-k)*p2)?div?p3}??? 时间复杂度?O(10*100^4)? ? 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];}??gmin ? 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 ----- const?w:array[1..n]?of?shortint=(1，2，3，5，10，20)； //不同砝码的重量 var?a:array?[1..n]?of?integer; //不同砝码的个数 f[0]:=1;?总重量个数(Ans) f[1]:=0;?第一种重量0; ? 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[0]:=1;???????????????????????? f[i]:=2*f[i-1]-f[i-1-m]????????? ? 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 (i0,j0,x[i]=y[j]); max{f[i,j-1]+f[i-1,j]}