ACM培训03-动态规划

1、10 动态规划.图1DAGCKBNPOMJFHELI312345214323142212223344阶段1阶段2阶段3阶段4阶段5义务：P是出发点，从P到A，求最短途径图1.思绪先看第5阶段，到达A点有两条路B A，需求2kmC A，需求3km令从P A的最短途径为P(A)；从P B的最短途径为P(B)；从P C的最短途径为P(C) P(A) = minP(B)+2, P(C)+3；P(B) = minP(D)+1, P(E)+2；P(C) = minP(E)+5, P(F)+4；.P(A) = minP(B)+2, P(C)+3；P(B) = minP(D)+1, P(E)+2；P(C) =

2、 minP(E)+5, P(F)+4； D 1 B 2 A 2 3 5 P(B) E C 4 P(C) F.P(N) = 2;P(O) = 3;上述递推公式通知我们，要求P(A)需求先求出阶段5中的P(B)和P(C)；要求 P(B) (或者P(C)，又要先求出阶段4中的 P(D) 和 P(E) (或P(F)和P(E)显然，要按照上述递推过程求解，需求倒过来，从P(P)出发，先求出第一阶段的P(O)和P(N)，再求第二阶段的P(K)，P(L)，P(M)；，最后得到P(A)。.选择数据构造，将每条路经的长度存在数组中。东西方向上的道路长度存在两维数组h43中规定数组的第一维为行号，第二维为列号。3

3、12345214323h43 = 3,2,3, 2,1,4, 3,4,5, 3,1,2 ;0121023.南北方向上道路长度存至数组v34中，也规定第一维为行号，第二维为列号。0123210223441241223v34 = 2, 2, 3, 4,4, 1, 2, 4,1, 2, 2, 3;.为了计算方便，将图1改为图2h30h31h32h20h21h22h10h11h12h00h01h02v20v21v22v23v10v11v12v13v00v01v02v03(3, 3)0213213yx图2.求解过程为从(0, 0)到(3, 3)求最短途径问题定义二维数组，P44=0,0,0,0,0,0,

4、0,0,0,0,0,0,0,0,0,0,第一维为行，第二维为列。这时P(O)为P01；P(N)为P10；P(A)为P33，以下为分阶段递推求解过程。对于阶段1:P00 = 0;P01 = P00+h00 = 0+3 = 3;P10 = P00+v00 = 0+2 = 2;.对于阶段2P11 = min P01+v01, P10+h10 = min3+1, 2+2 = 4P02 = P01+h10 = 3+2 = 5P20 = P10+v10 = 2+4 = 6对于阶段3P12 = min P02+v02, P11+h11 = min5+3, 4+1 = 5P03 = P02+h02 = 5+3

5、 = 8P21 = min P11+v11, P20+h20 = min4+1, 6+1 = 5P30 = P20+v20 = 6+1 = 7.对于阶段4P13 = min P03+v03, P12+h12 = min8+4, 5+4 = 9P22 = min P12+v12, P21+h21 = min5+2, 5+4 = 7P31 = min P21+v21, P30+h30 = min5+2, 7+3 = 7对于阶段5P23 = min P13+v13, P22+h22 = min9+4, 7+5 = 12P32 = min P22+v22, P31+h31 = min7+2, 7+1

6、= 8.最后P33 = min P23+v23, P32+h32 = min12+3, 8+2 = 10 综上，数组P的通项表示为Pij= min( ( pi-1j+vi-1j), (pij-1+hij-1) ) (i, j0)P0j=P0j-1+h0j-1( i=0, j0)Pi0=Pi-10+vi-10( i0, j=0)下面给出P数组中的数据01232100358245965712778103.数组P的通项表示为Pij= min( ( pi-1j+vi-1j), (pij-1+hij-1) ) (i, j0)P0j=P0j-1+h0j-1( i=0, j0)Pi0=Pi-10+vi-10

7、( i0, j=0).画出用动态规划思想求出的各个路口对P点的最小间隔。图中圆圈里就是这个间隔。箭头表示所寻得的最正确行走途径。图3312345214323142212223344026734575578891210P点A点图3. 参考程序如下.#include int min(int,int); int main() / 主函数 int h43= 3,2,3,2,1,4,3,4,5,3,1,2 ; int v34= 2,2,3,4,4,1,2,4,1,2,2,3 ; int p44= 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 ; p00=0; for(int j=1;j

8、4;j+)/y轴上的点 p0j=p0j-1+h0j-1; for(int i=1;i4;i+)/x轴上的点 pi0=pi-10+vi-10; . for(int i=1;i4;i+)/内部的点 for(int j=1;j4;j+) pij=min( ( pi-1j+vi-1j), (pij-1+hij-1) );cout“from P to A is p33=0;i-) i for(int j=0;j=3;j+) coutpij ; coutendl; return 0; 0 j .int min(int a,int b) if (ak-1 qr-k+1. p( l,r,k )=max d(

9、l, q ) * p( q+1, r ,k-1 ) q=l,l+1,r-k * q=l=0 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,0)=3 p( q+1,r,k-1 )=p( 1,6,2 ) (p( 0,6,3)|q=0) = 3 * p( 1,6,2 ) . q= l+1=1 * 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d(l,q)=d(0,1)= 32 p( q+1,r,k-1 )=p( 2,6,2 ) (p( 0,6,3)|q=1) = 32 * p( 2,6,2 ). q=l+2=2 * 3 2 1 5 1 2 5 0 1 2

10、3 4 5 6 d( l,q)=d(0,2)=321 p( q+1,r,1 )=p( 3,6,2 ) (p( 0,6,3)|q=2) = 321 * p( 3,6,2 ). q=l+3=3 * 3 2 1 5 1 2 5 0 1 2 3 4 5 6 d( l,q)=d(0,3)=3215 p( q+1,r,k-1 )=p( 4,6,2 ) ( p( 0,6,3)|q=3) = 3215 * p( 4,6,2 ).p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 *

11、 p( 4,6,2 ) / q=3 .p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 . p( 2,6,1 ) 1 5 1 2 5 1* 5125 2 3 4 5 6 1 5 1 2 5 15 * 125 2 3 4 5 6 1 5 1 2 5 15 1* 25 2 3 4 5 6 1 5 1 2 5 1512 *

12、5 2 3 4 5 6 . p(2,6,1) = max 1 * 5125 , 15 * 125 , 151 * 25 , 1512 * 5 = 7560 . p( 3,6,1 ) 5 1 2 5 5 * 125 3 4 5 6 5 1 2 5 51 * 25 3 4 5 6 5 1 2 5 5 12* 5 3 4 5 6 p( 3,6,1 )=max5*125, 51*25, 512*5 = 2560 . p( 4,6,1 ) 1 2 5 1 * 25 4 5 6 1 2 5 12 * 5 4 5 6 p( 4,6,1 ) = max 1 * 25, 12 * 5 = 60. p( 5,6,

13、1 ) 2 5 2 * 5 5 6 p(5,6,1) = 10. p( 2,6,2 ) 1 5 1 2 5 1* p(3,6,1 ) 2 3 4 5 6 1 5 1 2 5 15 * p(4,6,1) 2 3 4 5 6 1 5 1 2 5 151 * p(5,6,1) 2 3 4 5 6 p( 2,6,2 )= 1 * 2560, 15 * 60, 151 * 10 = 2560. p( 3,6,2 ) 5 1 2 5 5 * p(4,6,1 ) 3 4 5 6 5 1 2 5 51 * p(5,6,1) 3 4 5 6 p( 3,6,2 ) = 5 * 60 , 51 * 10 = 510

14、 . p( 4,6,2 ) 1 2 5 1 * 2 * 5 4 5 6 p( 4,6,2 ) = 10. p( 4,6,2 ) 1 2 5 1* p(5,6,1 ) 4 5 6 p(5,6,1) = 2 * 5 = 10 p(4,6,2) = 1 * p(5,6,1) = 10 .p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) =

15、 510 p( 4,6,2 ) = 60.p( 1,6,2 ) 2 1 5 1 2 5 2 * p(2,6,1 ) 1 2 3 4 5 6 2 1 5 1 2 5 21 * p(3,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 215 * p(4,6,1) 1 2 3 4 5 6 2 1 5 1 2 5 2151 * p(5,6,1) 1 2 3 4 5 6 . p( 1,6,2 )= max 2 * p( 2,6,1 ) , 21 * p( 3,6,1) , 215 * p( 4,6,1) , 2151 * p( 5,6,1) =max2*7560,21*2560,215*60,

16、2151*10 = 53760 .p( 0,6,3)= max 3 * p( 1,6,2 ) , / q=0 32 * p( 2,6,2 ) , / q=1 321* p( 3,6,2 ) , / q=2 3215 * p( 4,6,2 ) / q=3 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 2560 p( 3,6,2 ) = 510 p( 4,6,2 ) = 60.p( 0,6,3)= max 3 * 53760 , 32 * 2560 , 321* 510, 3215 * 60 = 163710 p( 1,6,2 ) = 53760 p( 2,6,2 ) = 256

17、0 p( 3,6,2 ) = 510 p( 4,6,2 ) = 60.分析形状转移方程p( l,r,k )=max d( l, q ) * p( q+1, r ,k-1 ) q=l,l+1,r-k 要求p( l,r,k )先要求p( q+1, r ,k-1 ) 是一个递归问题。 对p( l,r,k )而言，字符串下界是l上界是r，对p( q+1,r,k-1 )而言，字符串下界是q+1上界是r，乘号数为k-1这时很容易计算出要从多少个子项中选一个最大的出来： p( q+1,r,k-1 )=max d( q+1，t ) * p( t+1, r ,k-2) t=q+1,q+2,r-(k -1)递归的

18、边境是P(u,r,0)=d(u,r)=SuSu+1.Sr是不含乘号的数字串的值，可构建下表，事先将d(u,r)算出备用。. P(l,r,k) k=0 k !=0 d(l,r) q=l q=l+1 q=r-k p(l+1,r,k-1) 求max值 d(l,l)* p(l+1,r,k-1) d(l,r-k)* p(r-k+1,r,k-1) p(r-k+1,r,k-1) p(l+2,r,k-1) d(l,l+1)* p(l+2,r,k-1) . dij j 0 1 2 3 4 5 6 i 0 3 32 321 3215 32151 321512 3215125 1 2 21 215 2151 215

19、12 215125 2 1 15 151 1512 15125 3 5 51 512 5125 4 1 12 125 5 2 25 6 5. 怎样计算这张表 ? 分两步1.先算出j=6那一列的数： di6, i=0,1,2,3,4,5,6. d06=s = 3215125 去掉最高位3就是 d16= 215125 = 3215125 % 1000000 = s % 1000000 s1=1000000 = s % s1 s1= s1/10 d26= d16 % s1. s1=1000000; d06=s; for(int i=1; i=0; j- ) for(int i=0; i= j; i

20、+ ) dij=dij+1/10; . 参 考 程 序 #include / 预编译命令 #include / 预编译命令 using namespace std; / 运用名字空间 const int S=3215125; /定义常整数 int d77; /定义二维数组 . int P( int l, int r, int k ) /计算P函数值 if ( k=0) return dlr; int x, ans=0; for( int q=1; qans ) ans=x; return ans; .int main() memset( d,0,sizeof(d);/初始化数组元素为0 int

21、 s1=1000000; d06=s; for( int i=1; i=0; j- ) for( int i=0; i= j; i + ) dij=dij+1/10; coutP( 0,6,3 )3 k=1 m=3.m为柱子数，n为盘子数 k是下面盘子数 s(m,n)=min2*s(m,n-k)+s(m-1,k) k 1. s(m,n)=1, m=2, n=1 2. s(m,n)=1, m=3, n=1 3. s(m,n)=3, m=3, n=2 4. s(m,n)=3, m=4, n=2 5. s(m,n)=7, m=3, n=3 6. s(m,n)=5, m=4, n=3 . 1 2 4

22、5 from temp1 temp2 to 3. 分析 ： k值的选择是关键1. 问题的处理有假设干个阶段，是一个多步 决策的过程。 2. 对于阶段 b 而言，阶段 a 的处理与之无关, 相关的只是阶段 a 处理后的形状。问题的 阶段划分满足无后效性的要求。3. 问题的最优战略是各阶段最优子战略的组 合，假设问题 h 获得最优解，那么其在阶段a, b, c 上也必然获得最优解。问题满足动态 规划的最优性原理。. 动态规划普通式 min s(m,n-k)+s(m-1,k)+s(m,n-k) k k=1,2, m3 n1 s(m,n)= k=1 m=3 n1 1 m=2 n=1 0 其它 . m=

23、3, n=2 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,2)=min 2*s(3,2-1)+s(3-1,1) =min 2*s(3,1)+s(2,1) =min 2*1 + 1 = 3. m=3, n=3 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,3)=min 2*s(3,3-1)+s(3-1,1) =min 2*s(3,2)+s(2,1) =min 2*3 + 1 = 7. m=3, n=4 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,4)=min 2*s(3,4-1)+s(3-1

24、,1) =min 2*s(3,3)+s(2,1) =min 2*7 + 1 = 15. m=3, n=5 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,5)=min 2*s(3,5-1)+s(3-1,1) =min 2*s(3,4)+s(2,1) =min 2*15 + 1 = 31. m=3, n=6 k=1 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(3,6)=min 2*s(3,6-1)+s(3-1,1) =min 2*s(3,5)+s(2,1) =min 2*31 + 1 = 63 . m=4, n=3 , k=1, 2, 3

25、s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(4,3)=min 2*s(4,3-1)+s(4-1,1), 2*s(4,3-2)+s(4-1,2), 2*s(4,3-3)+s(4-1,3) =min 2*s(4,2)+s(3,1), 2*s(4,1)+s(3,2), 2*s(4,0)+s(3,3) =min 2*3 + 1, 2*1+3, 2*0+7 = 5. m=4, n=4 , k=1, 2, 3, 4 s(m,n)=min 2* s(m,n-k)+s(m-1,k) s(4,4)=min 2*s(4,4-1)+s(4-1,1), 2*s(4,4-2)+s(4-1,2),

26、 2*s(4,4-3)+s(4-1,3), 2*s(4,4-4)+s(4-1,4) =min 2*s(4,3)+s(3,1), 2*s(4,2)+s(3,2), 2*s(4,1)+s(3,3) , 2*s(4,0)+s(3,4) =min 2*5 + 1, 2*3+3, 2*1+7, 2*0+ 15 = 9 . s(4,5)=13, k=3 s(4,6)=17, k=3 s(4,7)=25, k=4 s(4,8)=33, k=4 s(4,9)=41, k=4. 思绪清楚了，请本人编出程序， 并运转经过。.Who Is In Front of MeTimeLimit: 1 Second Memo

27、ryLimit: 32 Megabyte Totalsubmit: 265 Accepted: 69 DescriptionThere are N(1=N=50000)students stand in a queue.We assume that every can only see the students that are in front of him and taller than him.For example, there are 6 students standing in a queue with height of4 3 1 2 5 2,begining from the

28、front student. In this example, student 3s height is 1, and he can see 2 persons. Student 6, although many students in front are taller than him, but he can only see the student with height of 5.Now, given the number of students in a queue, and the height of each, can you find the student that can see most persons.InputInput contains multiple test cases. The first