noip动态规划教学PPT

1、动态程序设计 动态规划动态规划 与递归程序相类，将对问题求解分解为对子问与递归程序相类，将对问题求解分解为对子问 题求解；不同之处在于把子问题的解存起来，题求解；不同之处在于把子问题的解存起来， 用空间换时间。用空间换时间。 例：例：fibonacci数数 uf(0)=0; f(1)=1; f(n)=f(n-1)+f(n-2); u递归递归: f(n-1)和和f(n-2)分别求到底一次分别求到底一次 u动态规划：用数组将前动态规划：用数组将前n-1个数存起来，每次只用个数存起来，每次只用 一个加法一个加法 fn = fn-1+fn-2 即可。即可。 例最短路径问题。下图中给出一个地图，地图中每

2、个顶点代表例最短路径问题。下图中给出一个地图，地图中每个顶点代表 一个城市，两个城市之间的连线表示道路，连线上的数值代表道路一个城市，两个城市之间的连线表示道路，连线上的数值代表道路 的长度。现在，想从城市的长度。现在，想从城市a到城市到城市e，怎样走路程最短，最短路程，怎样走路程最短，最短路程 的长度是多少？的长度是多少？ 现在，我们想从城市现在，我们想从城市a到达城市到达城市e。怎样走才能使得路径最短，最。怎样走才能使得路径最短，最 短路径的长度是多少？短路径的长度是多少？ 设：设：disx为城市为城市x到城市到城市e的最短路径长度（的最短路径长度（x表示任意一个城市）表示任意一个城市）;

3、mapi,j表示表示i，j 两个城市间的距离，若两个城市间的距离，若mapi,j=0，则两个城市不通。，则两个城市不通。 我们可以使用回溯来计算我们可以使用回溯来计算disx: var s:未访问的城市聚合；未访问的城市聚合； function search(who):integer; 求城市求城市who与城市与城市e的最短距离的最短距离 var i,j,min:integer; begin if who=e then search:=0 else begin min:=maxint; for i取遍所有城市取遍所有城市 do if (mapwho,i0) and (i in s) then

4、begin s:=s-i; 城市城市i已访问已访问 j:=mapwho,i+search(i); 计算城市计算城市e至城市至城市who的路径长度的路径长度 s:=s+i; 恢复城市恢复城市i未访问状态未访问状态 if jmin then min:=j; 若城市若城市e至城市至城市who的路径长度为目前最短，则记下的路径长度为目前最短，则记下 end; search:=min; 返回城市返回城市e至城市的最短路径长度至城市的最短路径长度 end; begin s:=所有城市；所有城市； disa:=search(a); 计算城市计算城市a城市城市e的最短路径长度的最短路径长度 writeln(d

5、ista); end. 这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外， 其他城市都要，所以时间复杂度为其他城市都要，所以时间复杂度为w(n!)，这是一个，这是一个“指数级指数级”的算法。的算法。 那么还有没有效率更高的解题方法呢？那么还有没有效率更高的解题方法呢？ 首先，我们来观察上述算法。在求首先，我们来观察上述算法。在求b1到到e的最短路径的时候，先求出从的最短路径的时候，先求出从c2 到到e的最短路径；而在求的最短路径；而在求b2到到e的最短路径的时候，又求了一遍从的最短路径的时候，又求了一遍从c2到到e

6、的最短路径。也就是说，从的最短路径。也就是说，从c2到到e的最短路径求了两遍。两样可以发现，的最短路径求了两遍。两样可以发现， 在求从在求从c1、c2到到e的最短路径的过程中，从的最短路径的过程中，从d1到到e的最短路径也被求了两的最短路径也被求了两 遍。而在整个过程中，从遍。而在整个过程中，从d1到到e的最短路径被求了四遍，这是多么大的一的最短路径被求了四遍，这是多么大的一 个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在记录在 案案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思，以便将来随时调用，则可以

7、避免这种重复计算。至此，一个新的思 路产生了，即由后往前依次推出每个路产生了，即由后往前依次推出每个dis值，直到推出值，直到推出disa为止为止。 阶段的划分具有如下性质：阶段的划分具有如下性质： 阶段阶段i的取值只与阶段的取值只与阶段i+1有关，阶段有关，阶段i+1的取值只对阶段的取值只对阶段i的取值的取值 产生影响；产生影响； 每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。 abcde 阶段阶段1阶段阶段2阶段阶段3阶段阶段4阶段阶段0 我们从阶段我们从阶段4的城市的城市e出发，按照阶段的顺序倒推至阶段出发，按照阶段的顺序倒推至阶

8、段0的城市的城市a。 在求解的各个阶段，利用了在求解的各个阶段，利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k阶段的城市阶段的城市x x。 ),( ,min 1 gyxyxmapydis ky 阶段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 abcde 阶段阶段1 阶段阶段2 阶段阶段3阶段阶段4阶段阶段0 我们从阶段我们从阶段4的城市的城市e出发，按照阶段的顺序倒推至阶段出

9、发，按照阶段的顺序倒推至阶段0的城市的城市a。 在求解的各个阶段，利用了在求解的各个阶段，利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k阶段的城市阶段的城市x x。 ),( ,min 1 gyxyxmapydis ky 阶段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 2 3 4 abcde 阶段阶段1 阶段阶段2 阶段阶段3阶段阶段4阶段阶段0 我们从阶段我们从阶段4的城市的

10、城市e出发，按照阶段的顺序倒推至阶段出发，按照阶段的顺序倒推至阶段0的城市的城市a。 在求解的各个阶段，利用了在求解的各个阶段，利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k阶段的城市阶段的城市x x。 ),( ,min 1 gyxyxmapydis ky 阶段的城市集 23 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 3 4 4 6 abcde 阶段阶段1 阶段阶段2 阶段阶段3阶段

11、阶段4阶段阶段0 我们从阶段我们从阶段4的城市的城市e出发，按照阶段的顺序倒推至阶段出发，按照阶段的顺序倒推至阶段0的城市的城市a。 在求解的各个阶段，利用了在求解的各个阶段，利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k阶段的城市阶段的城市x x。 ),( ,min 1 gyxyxmapydis ky 阶段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6 12 2 2 3 3 2 3 4 0 2 3 4 3 4 6

12、7 7 8 abcde 阶段阶段1 阶段阶段2 阶段阶段3阶段阶段4阶段阶段0 我们从阶段我们从阶段4的城市的城市e出发，按照阶段的顺序倒推至阶段出发，按照阶段的顺序倒推至阶段0的城市的城市a。 在求解的各个阶段，利用了在求解的各个阶段，利用了k阶段与阶段与k+1阶段之间的如下关系阶段之间的如下关系 diskx= dis4e=0 k=4k=4，3 3，0 0，其中，其中disdisk kx x指指k k阶段的城市阶段的城市x x。 ),( ,min 1 gyxyxmapydis ky 阶段的城市集 e d3 d1 d2 c1 c3 c2a b3 b2 b1 5 4 2 6 3 4 6 5 6

13、12 2 2 3 3 2 3 4 0 2 3 4 3 4 6 7 7 8 10 abcde 阶段阶段1 阶段阶段2 阶段阶段3阶段阶段4阶段阶段0 由此得出程序由此得出程序 : dise0； for k3 downto 0 do3 downto 0 do for x for x取遍取遍k阶段的所有城市阶段的所有城市do begin disx； for y取遍取遍k+1阶段的所有城市阶段的所有城市do if disy+mapx,yfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; 状态转移方程：状态转移方程：fi,j:=max(fi

14、+1,j+1, fi+1,j)+ai,j; program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1.maxn,1.maxn of integer; n:integer; procedure init; procedure main; procedure print; begin init; main; print; end. procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n);

15、for i:=1 to n do begin for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure print; var i,ans:integer; begin assign(output,fon); rewrite(output); writeln(f1,1); close(output); end; procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to

16、 i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end; program triple; const fin=d:input.txt; fon=d:output.txt; maxn=100; var f,a:array1.maxn,1.maxn of integer; n:integer; procedure init; var i,j:integer; begin assign(input,fin);reset(input); readln(n); for i:=1 to n do begin

17、for j:=1 to i do read(ai,j); readln; end; close(input); end; procedure main; var i,j:integer; begin for i:=1 to n do fn,i:=an,i; for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j; end; procedure print; var i,ans:integer; begin assign(output,fon

18、); rewrite(output); writeln(f1,1); close(output); end; begin init; main; print; end. 例例2 给定数列给定数列a1,a2,an，求最长递减子序列。，求最长递减子序列。 输入数据输入数据 n和和n个整数（个整数（n=1000）。）。 输出数据输出数据 最长递减子序列。最长递减子序列。 算法分析算法分析 ai=数列的第数列的第i个数；个数； si=以以ai结尾的最长递减子序列长度；结尾的最长递减子序列长度； si=maxsk+1 0=kai； 边界条件：边界条件：s0=0； answer=maxsi, 1=i=n。

19、 a: 76 8 9 6 20 19 18 69 3 s: 1 2 2 3 2 3 4 2 5 算法分析算法分析 ai=数列的第数列的第i个数；个数； si=以以ai结尾的最长递减子序列长度；结尾的最长递减子序列长度； a: 76 8 9 6 20 19 18 69 3 s: 1 2 2 3 2 3 4 2 5 状态转移方程：状态转移方程：si=maxsk+1 0=kai； 边界条件：边界条件：s0=0； answer=maxsi, 1=iai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(an

20、swer); si=maxsk+1 0=kai； 边界条件：边界条件：s0=0； answer=maxsi, 1=iai) and (sk+1si) then si:=sk+1; if (sianswer) then answer:=si; end; writeln(answer); end. program ex6_2_2; var n,i,k,answer:integer; a:array1.1000 of integer; s,last:array0.1000 of integer; size:integer; q:array1.1000 of integer; begin read(n

21、); for i:=1 to n do read(ai); s0:=0; answer:=0; for i:=1 to n do begin si:=0; for k:=0 to i-1 do if (k=0) or (akai) and (sk+1si) then begin si:=sk+1; lasti:=k; end; end; for i:=1 to n do if (sianswer) then begin answer:=si; k:=i; end; size:=0; repeat inc(size); qsize:=k; k:=lastk; until k=0; writeln

22、(answer); for i:=size downto 1 do write(qi, ); writeln; end. 转移方程转移方程 数的计算数的计算(02)：fi:=1+f1+f2+fi div 2 过河卒过河卒(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)mod 1000007 数字游戏数字游戏(03 )：fmin1p,i,j=minfmin1p-1,i,k*gk+1,j (i=k=j-1)