noip动态规划教学PPT.ppt

动态程序设计,动态规划,与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。例：fibonacci数f(0)=0;f(1)=1;f(n)=f(n-1)+f(n-2);递归:f(n-1)和f(n-2)分别求到底一次动态规划：用数组将前n-1个数存起来，每次只用一个加法fn=fn-1+fn-2即可。,例最短路径问题。下图中给出一个地图，地图中每个顶点代表一个城市，两个城市之间的连线表示道路，连线上的数值代表道路的长度。现在，想从城市a到城市e，怎样走路程最短，最短路程的长度是多少？现在，我们想从城市a到达城市e。怎样走才能使得路径最短，最短路径的长度是多少？,设：disx为城市x到城市e的最短路径长度（x表示任意一个城市）;mapi,j表示i，j两个城市间的距离，若mapi,j=0，则两个城市不通。我们可以使用回溯来计算disx:,vars:未访问的城市聚合；functionsearch(who):integer;求城市who与城市e的最短距离vari,j,min:integer;beginifwho=ethensearch:=0elsebeginmin:=maxint;fori取遍所有城市doif(mapwho,i0)and(iins)thenbegins:=s-i;城市i已访问j:=mapwho,i+search(i);计算城市e至城市who的路径长度s:=s+i;恢复城市i未访问状态ifjfi+1,j+1thenfi,j:=fi+1,j+ai,jelsefi,j:=fi+1,j+1+ai,j;end;,programtriple;constfin=d:input.txt;fon=d:output.txt;maxn=100;varf,a:array1.maxn,1.maxnofinteger;n:integer;procedureinit;vari,j:integer;beginassign(input,fin);reset(input);readln(n);fori:=1tondobeginforj:=1toidoread(ai,j);readln;end;close(input);end;proceduremain;vari,j:integer;beginfori:=1tondofn,i:=an,i;fori:=n-1downto1doforj:=1toidoiffi+1,jfi+1,j+1thenfi,j:=fi+1,j+ai,jelsefi,j:=fi+1,j+1+ai,j;end;procedureprint;vari,ans:integer;beginassign(output,fon);rewrite(output);writeln(f1,1);close(output);end;begininit;main;print;end.,例2,给定数列a1,a2,an，求最长递减子序列。输入数据n和n个整数（nai；边界条件：s0=0；answer=maxsi,1=i=n。,a:76896201918693,s:122323425,算法分析,ai=数列的第i个数；si=以ai结尾的最长递减子序列长度；,a:76896201918693,s:122323425,状态转移方程：si=maxsk+10ai；边界条件：s0=0；answer=maxsi,1si)thensi:=sk+1;if(sianswer)thenanswer:=si;end;writeln(answer);,si=maxsk+10ai；边界条件：s0=0；answer=maxsi,1si)thensi:=sk+1;if(sianswer)thenanswer:=si;end;writeln(answer);end.,programex6_2_2;varn,i,k,answer:integer;a:array1.1000ofinteger;s,last:array0.1000ofinteger;size:integer;q:array1.1000ofinteger;beginread(n);fori:=1tondoread(ai);s0:=0;answer:=0;fori:=1tondobeginsi:=0;fork:=0toi-1doif(k=0)or(akai)and(sk+1si)thenbeginsi:=sk+1;lasti:=k;end;end;,fori:=1tondoif(sianswer)thenbeginanswer:=si;k:=i;end;size:=0;repeatinc(size);qsize:=k;k:=lastk;untilk=0;writeln(answer);fori:=sizedownto1dowrite(qi,);writeln;end.,转移方程,数的计算(02)：fi:=1+f1+f2+fidiv2过河卒(02)：fi,j=fi-1,j+fi,j-1栈(noip2003)：fi,j=fi-1,j+1+fi-1,j;传球游戏(08)：fi,k:=fi-1,k-1+fi+1,k-1;装箱问题(01)：f(x)=maxf(x-wi)+ui当x=wi,1=i=n采药(05)：f(i,x)=max(f(i,x-wi)+ui,f(i-1,x);f(n,m)开心的金明(06)摆花(12)：fi,j:=(fi,j+fi-1,j-k)mod1000007数字游戏(03)：fmin1p,i,j=minfmin1p-1,i,k*gk+1,j(i=k=j-1)fmax1p,i,j=maxfmax1p-1,i,k*gk+1,j(i=k=j-1)乘积最大(00):合并类道路游戏(09)：f(i)=maxf(x-1)-cost(posk,x)+sumk,i-sumk,x-1|i-p=xi,1=i=m,0=k=n守望者的逃离(07)表达式的值(11)：,树型动态规划,四、最大利润题目描述政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。告诉你每个火车站的利润，部你可以获得的最大利润为多少？例如下图是火车站网络：最佳投资方案是在1,2,5,6这4个火车站开饭店可以获得利润为90。输入