tyvj动态规划题解

《tyvj动态规划题解》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Tyvj动态规划类题解这是我在做tyvj题库时的一些想法，希望会对一些做题有困难的同学一些帮助。P1004滑雪地势低的格子必由地势高的格子滑下，若按照地势从高到低处理每个格子的滑行最大长度，不会有后效性的，故可以使用动态规划求解。先对map【I,j】进行排序，然后从大到小进行动态规划，用f【I,j】表示（I,j）位置可以滑行的最大长度，F【I,j】：=max（f【x0，y0】+1）（其中（I,j）和（x0，y0）相邻且map【I,j】

2、r;a:array[0..102,0..102]ofinteger;f:array[0..105,0..105]ofinteger;g:array[0..10005,0..2]ofinteger;beginreadln(r,c);fori:=0tor+1doforj:=0toc+1dobegina[i,j]:=maxint;f[i,j]:=0;end;k:=0;fori:=1tordoforj:=1tocdobeginread(a[i,j]);k:=k+1;g[k,0]:=a[i,j];g[k,1]:=i;g[k,2]:=j

3、;end;fori:=1tor*c-1doforj:=i+1tor*cdoifg[j,0]f[x,y]thenf[x,y]:=f[x-1,y]+1;ifa[x+1,y]

4、x+1,y]+1>f[x,y]thenf[x,y]:=f[x+1,y]+1;ifa[x,y-1]f[x,y]thenf[x,y]:=f[x,y-1]+1;ifa[x,y+1]f[x,y]thenf[x,y]:=f[x,y+1]+1;iff[x,y]>lenthenlen:=f[x,y];end;writeln(len);end.本题还可以使用记忆化搜索。P1005采药最简单的01背包问题，f【I,j】表示前i草药，前j时间的采得的

5、最大价值；状态转移方程：F【I,j】：=max（f【i-1，j】，f【i-1，j-t【i】】+w【i】】）；P1008传球游戏F【I,j】表示第i次传球到编号为j的同学手中的方案数，它总是由i-1次时j+1和j-1得到的，则F【I,j】：=f【I-1,j-1】+f【i-1，j+1】；边界：F【0,1】：=1；f【0,1..n】：=0；要注意编号为1和n之间的处理（这哪是什么动态规划嘛，明明就一递推!?）P1011传纸条这是一道稍有难度的dp问题，它的本质是求不相交的两条最大路径，m*n的矩阵可以根据对角线划分为m+n-1个阶

6、段，分别为i:=1..m+n-1。根据矩形的性质，第i阶段横坐标为x的数格纵坐标为i+1-x，故可以将状态量减少为3个，即f【i，x1，x2】表示第i阶段时两条路径横坐标分别在x1和x2时路径经过的权值最大值，这样F【i，x1,x2】：=max（f【i-1，x1+d1，x2+d2】+w【x1,y1】+w【x2,y2】）（其中d1，d2=0，-1，表示当前格的左格和上格）（这是双管齐下啊，纠结了好半天。。。）代码：constb1:array[1..4]ofinteger=(0,1,0,1);b2:array[1..4]ofin

7、teger=(0,1,1,0);varf:array[0..100,0..50,0..50]oflongint;a:array[0..50,0..50]oflongint;g:array[0..100,1..2]ofinteger;m,n,i,j,x1,x2,k:longint;procedureinit;beginreadln(m,n);fori:=1tomdoforj:=1tondoread(a[i,j]);fori:=1tom+n-1dobeginifi<=ntheng[i,1]:=1elseg[i,1]:=i+1-n

8、;ifi<=mtheng[i,2]:=ielseg[i,2]:=m;end;fori:=1tom+n-1doforx1:=g[i,1]tog[i,2]doforx2:=g[i,1]tog[i,2]dof[i,x1,x2]:=0;end;procedureDP;beginfori:=2tom