动态规划状态转移方程

1、1.资源问题1-机器分配问题FI,j:=max(fi-1,k+wi,j-k)2.资源问题2-01背包问题FI,j:=max(fi-1,j-vi+wi,fi-1,j); 3.线性动态规划1-朴素最长非降子序列Fi:=maxfj+14.剖分问题1-石子合并Fi,j:=min(fi,k+fk+1,j+sumi,j);5.剖分问题2-多边形剖分FI,j:=min(fi,k+fk,j+ak*aj*ai);6.剖分问题3-乘积最大fi,j:=max(fk,j-1*multk,i);7.资源问题3 -系统可靠性(完全背包)Fi,j:=maxfi-1,j-ci*k*PI,x8.贪心的动态规划1-快餐问题 Fi

2、,j表示前i条生产线生产j个汉堡,k个薯条所能生产的最多饮料, 则最多套餐ans:=minj div a,k div b,fI,j,k div cFi,j,k:=maxfi-1,j,k+(Ti-(j-j)*p1-(k-k)*p2) div p3 时间复杂度 O(10*1004) 9.贪心的动态规划2-过河 fi=minf(i-k) (not stonei) f(i-k)+1 (stonei); +贪心压缩状态10.剖分问题4-多边形-讨论的动态规划Fi,j:=max正正 fI,k*fk+1,j; 负负 gI,k*fk+1,j; 正负 gI,k*fk+1,j; 负正 fI,k*gk+1,j; g

3、为min11.树型动态规划1-加分二叉树 (从两侧到根结点模型)FI,j:=maxfI,k-1*fk+1,j+ck12.树型动态规划2-选课 (多叉树转二叉树,自顶向下模型)FI,j表示以i为根节点选j门功课得到的最大学分fi,j:=maxfti.l,k+fti.r,j-k-1+ci13.计数问题1-砝码称重const w:array1.n of shortint=(1，2，3，5，10，20)；/不同砝码的重量var a:array 1.n of integer;/不同砝码的个数f0:=1; 总重量个数(Ans)f1:=0; 第一种重量0;ff0+1=fj+k*wj;(1=i=n; 1=j=

4、f0; 1=k=ai;)14.递推天地1-核电站问题f-1:=1; f0:=1; fi:=2*fi-1-fi-1-m 15.递推天地2-数的划分fi,j:=fi-j,j+fi-1,j-1;16.最大子矩阵1-一最大01子矩阵fi,j:=min(fi-1,j,vi,j-1,vi-1,j-1)+1; ans:=maxvalue(f); 17.判定性问题1-能否被4整除g1,0:=true; g1,1:=false; g1,2:=false; g1,3:=false;gi,j:=gi-1,k and (k+ai,p) mod 4 = j) 18.判定性问题2-能否被k整除fI,jni mod k:=

5、fi-1,j; -k=j=k; 1=i0,j0,xi=yj);maxfi,j-1+fi-1,j (i0,j0,xiyj);let(nm); (n=length(a); m:=length(b);for i:= 1 to n do begin x:=-1; p:=1; for j:= 1 to m do if ai=bj then begin x:=p; while flagj,x and (fj,xai) do inc(x); p:=x; fj,x:=ai; flagj,x:=true; end else if (x-1) and flagj-1,x and (not flagj,x) or

6、(fj-1,xfj,x) then begin fj,x:=fj-1,x; flagj,x:=true; end else x:=-1; end; ok:=false; for i:= m downto 1 do if flagm,i then begin writeln(i); ok:=true; break; end;if not ok then writeln(0);22.最大子矩阵2-最大带权01子矩阵O(n2*m)枚举行的起始，压缩进数列，求最大字段和，遇0则清零fi:=max(fi-1+ai,ai) readln(n,m); for i:= 1 to n do for j:= 1

7、to m do read(ai,j); ans:=-maxlongint; for i:= 1 to n do begin fillchar(b,sizeof(b),0); fillchar(u,sizeof(u),0); for j:= i to n do begin max:=0; for k:= 1 to m do begin if (aj,k0) and (not uk) then begin inc(bk,aj,k); inc(max,bk) end else begin max:=0; uk:=true; end; if maxans then ans:=max; end; end

8、; end;23. 资源问题4-装箱问题(判定性01背包)fj:=(fj or fj-vi);注:这里将数字三角形的意义扩大凡状态转移为图形,跟其上面阶段和前面状态有关都叫数字三角形:)24.数字三角形1-朴素数字三角形fi,j:=max(fi+1,j+aI,j,fi+1,j+1+ai,j); 25.数字三角形2-晴天小猪历险记之Hill同一阶段上暴力动态规划ifi,j:=min(fi,j-1,fI,j+1,fi-1,j,fi-1,j-1)+ai,j26.双向动态规划1数字三角形3-小胖办证fi,j:=max(fi-1,j+ai,j,fi,j-1+ai,j,fi,j+1+ai,j)27. 数字

9、三角形4-过河卒/边界初始化fi,j:=fi-1,j+fi,j-1;28.数字三角形5-朴素的打砖块fi,j,k:=max(fi-1,j-k,p+sumi,k,fi,j,k);29.数字三角形6-优化的打砖块fI,j,k:=maxgi-1,j-k,k-1+sumI,k30.线性动态规划3-打鼹鼠fi:=fj+1;(abs(xi-xj)+abs(yi-yj)=3)39递推天地9-Catalan数列一般形式1,1,2,5,14,42,132fn:=C(2k,k) div (k+1);40递推天地10-彩灯布置排列组合中的环形染色问题fn:=fn-1*(m-2)+fn-2*(m-1); (f1:=m

10、; f2:=m(m-1);41线性动态规划4-找数线性扫描 sum:=fi+gj; (if sum=Aim then getout; if sumAim then inc(i) else inc(j);) 42线性动态规划5-隐形的翅膀min:=minabs(wi/wj-gold);if wi/wjl) then exit(WQ) else getS:=(l mod n)*k2*sqr(l div n+1)+ (n-l mod n)*k2*sqr(l div n)+ k1*sqr(l);end;if x+S(x,k)=fi,q,p then break else fi,q,p:=x+S(x,k

11、);inc(k);计数问题2-陨石的秘密（排列组合中的计数问题）Ansl1,l2,l3,D:=fl1+1,l2,l3,D+1-fl1+1,l2,l3,D;Fl1,l2,l3,D:=Sigma(fo,p,q,d-1*fl1-o,l2-p,l3-q,d);线性动态规划-合唱队形两次Fi:=maxfj+1枚举中央结点资源问题-明明的预算方案：加花的动态规划fi,j:=max(fi,j,fl,j-vi-vfbi-vfai+vi*pi+vfbi*pfbi+vfai*pfai);资源问题-化工场装箱员树形动态规划-聚会的快乐fi,2:=max(fi,0,fi,1);fi,1:=sigma(fti.son,

12、0);fi,0:=sigma(fti.son,3);树形动态规划-皇宫看守fi,2:=max(fi,0,fi,1);fi,1:=sigma(fti.son,0);fi,0:=sigma(fti.son,3);递推天地-盒子与球fi,1:=1;fi,j:=j*(fi-1,j-1+fi-1,j);双重动态规划-有限的基因序列fi:=minfj+1gc,i,j:=(ga,i,j and gb,i,j) or (gc,i,j)最大子矩阵问题-居住空间 fi,j,k:=min(min(min(fi-1,j,k,fi,j-1,k), min(fi,j,k-1,fi-1,j-1,k), min(min(fi

13、-1,j,k-1,fi,j-1,k-1), fi-1,j-1,k-1)+1;线性动态规划-日程安排fi:=maxfj+PI; (ejsi)递推天地-组合数CI,j:=Ci-1,j+CI-1,j-1CI,0:=1树形动态规划-有向树k中值问题FI,r,k:=maxmaxfli,I,j+fri,I,k-j-1,ffli,r,j+fri,r,k-j+wI,r树形动态规划-CTSC 2001选课FI,j:=wi(if iP)+fli,k+fri,m-k(0km)(if li0)线性动态规划-多重历史fi,j:=sigmafi-k,j-1(if checked)背包问题(+-1背包问题+回溯)-CEOI

14、1998 Substractfi,j:=fi-1,j-ai or fi-1,j+ai线性动态规划(字符串)-NOI 2000 古城之谜fi,1,1:=minfi+length(s),2,1, fi+length(s),1,1+1fi,1,2:=minfi+length(s),1,2+wordss,fi+length(s),1,2+wordss线性动态规划-最少单词个数fi,j:=maxfI,j,fu-1,j-1+l线型动态规划-APIO2007 数据备份状态压缩剪掉每个阶段j前j*2个状态和j*2+200后的状态贪心动态规划fi:=min(gi-2+si,fi-1);树形动态规划-APIO20

15、07 风铃fi:=fl+fr+1 (if clcr)gi:=1(dldr) 0(dl=dr)gl=gr=1 then Halt;地图动态规划-NOI 2005 adv19910Ft,i,j:=maxft-1,i-dxdt,j-dydk+1,ft-1,i,j;地图动态规划-优化的NOI 2005 adv19910Fk,i,j:=maxfk-1,i,p+1 j-bk=p=p=l, 1=q=p;地图动态规划-vijos某题FI,j:=min(fi-1,j-1,fI,j-1,fi-1,j);最大子矩阵问题-最大字段和问题fi:=max(fi-1+bi,bi); f1:=b1最大子矩阵问题-最大子立方体

16、问题枚举一组边i的起始，压缩进矩阵 BI,j+=ax,I,j枚举另外一组边的其实，做最大子矩阵括号序列-线型动态规划fI,j:=min(fI,j,fi+1,j-1(sisj=”()”or(”),fI+1,j+1+1 (sj=”(”or” , fI,j-1+1(sj=”)”or” )棋盘切割-线型动态规划fk,x1,y1,x2,y2=minminfk-1,x1,y1,a,y2+sa+1,y1,x2,y2,fk-1,a+1,y1,x2,y2+sx1,y1,a,y2min概率动态规划-聪聪和可可(NOI2005)x:=ppi,j,jfI,j:=(fx,bj,k+fx,j)/(lj+1)+1fI,i=

17、0fx,j=1概率动态规划-血缘关系 我们正在研究妖怪家族的血缘关系。每个妖怪都有相同数量的基因，但是不同的妖怪的基因可能是不同的。我们希望知道任意给定的两个妖怪之间究竟有多少相同的基因。由于基因数量相当庞大，直接检测是行不通的。但是，我们知道妖怪家族的家谱，所以我们可以根据家谱来估算两个妖怪之间相同基因的数量。 妖怪之间的基因继承关系相当简单：如果妖怪C是妖怪A和B的孩子，则C的任意一个基因只能是继承A或B的基因，继承A或B的概率各占50。所有基因可认为是相互独立的，每个基因的继承关系不受别的基因影响。 现在，我们来定义两个妖怪X和Y的基因相似程度。例如，有一个家族，这个家族中有两个毫无关系

18、(没有相同基因)的妖怪A和B，及它们的孩子C和D。那么C和D相似程度是多少呢？因为C和D的基因都来自A和B，从概率来说，各占50。所以，依概率计算C和D平均有50的相同基因，C和D的基因相似程度为50。需要注意的是，如果A和B之间存在相同基因的话，C和D的基因相似程度就不再是50了。 你的任务是写一个程序，对于给定的家谱以及成对出现的妖怪，计算它们之间的基因相似程度。FA, B=(fA0, B+PA1, B)/2fI,i=1fI,j=0(I,j无相同基因)线性动态规划-决斗FI,j=(fI,j and fk,j) and (eI,k or ej,k),ikNb则标0否则标1，用二进制状态压缩进

19、k中，在这种情况下的最小花费FI,j,k:=minfl,u,k and (si(i-1)+w1,fr,j-u,k and(si(i-1)树形动态规划-IOI2005 河流Fi:=max记忆化搜索-Vijos某题,忘了Fpre,h,m:=sigmaSDP(I,h+1,M+i) (pre=i=M1)状态压缩动态规划-APIO 2007 动物园fI,k:=fi-1,k and not (1=0 then Min(fi,j,fi-1,j-k+time(i,k);背包问题- USACO Raucous Rockers多个背包，不可以重复放物品，但放物品的顺序有限制。 FI,j,k表示决策到第i个物品、第

20、j个背包，此背包花费了k的空间。fI,j,k:=max(fI-1,j,k,fI-1,j,k-ti+pi,fi-1,j-1,maxtime-ti) 多进程动态规划-巡游加拿大（IOI95、USACO）di,j=maxdk,j+1(ak,i & jki),dj,k+1(aI,j & (kj分析状态(i,j)，它可能是(k,j)(jki)中k到达i得到（方式1），也可能是(j,k)(kj)中k超过j到达i得到（方式2）。但它不能是(i,k)(kj)中k到达j得到，因为这样可能会出现重复路径。即使不会出现重复路径，那么它由(j,k)通过方式2同样可以得到，所以不会遗漏解 时间复杂度O(n3) 动态规划-ZOJ cheesefi,j:=fi-kk*zlu,1,j-kk*zlu,2+ai-kk*zlu,1,j-kk*zlu,2动态规划-NOI 2004 berry 线性FI,1:=siFI,j:=maxminsi-sl-1,fl-1,j-1 (2jk, jli)动态规划-NOI 2004 berry 完全无向图FI,j:=fi-1,j or (jwi) and (fi-1,j-wi)动态规划-石子合并 四边形不等式优化mi,j=maxmi+1,j, mi,j-1+ti,j 动态规划-CEOI 2005