动态规划状态转移方程工科.docVIP

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];} 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 -----砝码称重 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]}} (i0,j0,x[i]y[j]); let(nm); (n=length(a); m:=len