tyvj动态规划题解.doc

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】map【x0y0】）； 代码：var i,t,j,len,r,c,k,x,y,l:integer; a:array0.102,0.102of integer; f:array0.105,0.105of integer; g:array0.10005,0.2of integer;begin readln(r,c); for i:=0 to r+1 do for j:=0 to c+1 do begin ai,j:=maxint; fi,j:=0; end; k:=0; for i:=1 to r do for j:=1 to c do begin read(ai,j); k:=k+1; gk,0:=ai,j; gk,1:=i; gk,2:=j; end; for i:=1 to r*c-1 do for j:=i+1 to r*c do if gj,0gi,0 then begin for k:=0 to 2 do begin t:=gi,k; gi,k:=gj,k; gj,k:=t; end; end; len:=0; for l:=1 to r*c do begin x:=gl,1;y:=gl,2; fx,y:=1; if ax-1,yfx,y then fx,y:=fx-1,y+1; if ax+1,yfx,y then fx,y:=fx+1,y+1; if ax,y-1fx,y then fx,y:=fx,y-1+1; if ax,y+1fx,y then fx,y:=fx,y+1+1; if fx,ylen then len:=fx,y; end; writeln(len);end.本题还可以使用记忆化搜索。P1005 采药 最简单的01背包问题，f【I,j】表示前i草药，前j时间的采得的最大价值；状态转移方程：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个阶段，分别为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，表示当前格的左格和上格） （这是双管齐下啊，纠结了好半天。） 代码：const b1:array1.4of integer=(0,1,0,1); b2:array1.4of integer=(0,1,1,0);var f:array0.100,0.50,0.50of longint; a:array0.50,0.50of longint; g:array0.100,1.2of integer; m,n,i,j,x1,x2,k:longint;procedure init; begin readln(m,n); for i:=1 to m do for j:=1 to n do read(ai,j); for i:=1 to m+n-1 do begin if i=n then gi,1:=1 else gi,1:=i+1-n; if i0)and(i+1-x2+b2k0) then if fi-1,x1-b1k,x2-b2k+ax1,i+1-x1+ax2,i+1-x2fi,x1,x2 then fi,x1,x2:=fi-1,x1-b1k,x2-b2k+ax1,i+1-x1+ax2,i+1-x2; writeln(fm+n-2,m-1,m); end;begin /assign(input,paper.in);reset(input); init; DP; /close(input);end.P1013 找啊找啊找GF 简单的说这就是二维费用的背包问题， F【i，b，p，1】和F【i，b，p，2】分别表示对于前i个MM，用b的RMB和p的RP能泡到的最多MM及对应用得time，可以将i状态去掉以节省空间，这是我程序中的关键语句： if (fb-rmbi,p-rpi,1+1fb,p,1)or (fb-rmbi,p-rpi,1+1=fb,p,1)and (fb-rmbi,p-rpi,2+timeifb,p,1)or (fb-rmbi,p-rpi,1+1=fb,p,1)and (fb-rmbi,p-rpi,2+timeimm)or(fb,p,1=mm)and(fb,p,2t) then begin mm:=fb,p,1; t:=fb,p,2; end; end;begin /assign(input,mm.in);reset(input); init; dp; writeln(t); /close(input);end. 这其实是最简单的背包问题费用加一维，不要被这么多的变量给吓到了；P1015 公路乘车 用f【i】表示行i公里用的最少money；F【i】：=min（f【i-k】+p【k】） k：=1.10P1016 装箱问题 又是01背包，但有一点不同，f【I,j】表示第i个物品能否装到j的空间里面，能就等于TRUE不然就等于FALSE， F【I,j】：=f【i-1，j】 or f【i-1，j-v【i】；最后在通过比较就可以得到答案；P1024 外星人的密码数字 这是字符串处理加上最长不下降子序列 F【i】：=max（f【j】+1） j：=1.i-1；and （a【j】a【i】） 对于字符串的处理开个数组就行了； 看看我的程序吧：var k,i:integer; st1,st2:string; s:array1.100of string; g:array1.100of integer; p:array0.30of integer;procedure init; var i,j,l,x:integer; begin /assign(input,alion.in);reset(input); readln(st1); for i:=1 to 26 do begin x:=ord(st1i)-96; px:=i; end; readln(st2); l:=length(st2); k:=1; g1:=0; for i:=1 to l do if st2i= then begin k:=k+1; gk:=i; end; gk+1:=l+1; for i:=1 to k do begin si:=; for j:=gi+1 to gi+1-1 do si:=si+st2j; end; /close(input); end;function len(str:string):integer; var i,j,l:integer; f:array0.1000of integer; begin l:=length(str); len:=1; for i:=1 to l do begin fi:=1; for j:=1 to i-1 do if (pord(strj)-96fi) then fi:=fj+1; if filen then len:=fi; end; end;procedure main; var i:integer; begin init; for i:=1 to k do write(len(si); writeln; end;begin main;end.P1028 Bessie的体重问题 又是背包，和采药差不多的P1044 数字三角形 很简单，但还是说下，f【I,j】表示（I,j）位置的最大值， F【I,j】：=max（f【i-1，j】，f【i-1，j-1】）+a【I,j】；P1047 乘积最大 这道题麻，来看看别人很详细的题解=由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，只能采用高精度运算，限于篇幅，对于高精度的加法运算、乘法运算和比较大小的运算，这里不作介绍，只是对x的最佳插入方式进行探讨：假设s1si(2in)中插入j个*。其中s1sk中插入了j-1个*，即乘式中的第j+1项为sk+1si(jki-1)： 设ansi，j长度为i的数串中插入j个*的最大乘积（整型数组）。显然 ansi，0=sis1对应的整型数组； ansi，j=ansk，j-1*sk+1si （1in， 1jmini-1，m） ansn,m即为其解。 由于乘式中第j+1项sk+1si为常量，因此要使得ansi，j最大，则s1sk中插入j-1个*的乘积必须最大；同样，为了寻找第j个*的最佳插入位置，必须一一查阅子问题ansj，j-1ansi-1，j-1的解。显然该问题具备最优子结构和重叠子问题的特征，适用于动态程序设计方法求解。设阶段i：数串的长度（2in）状态j：长度为i的数串中插入的*个数（1jmini-1，m）决策k：第j个*的最佳插入位置（jki-1）由此得出算法：输入n，m和数串s；for i1 to n do ansi，0s1.si对应的整数数组；for i2 to n do 阶段：枚举数串的长度 for j1 to mini-1，m do 状态：枚举长度为i的数串中插入的*个数 for kj to i-1 do 决策：枚举第j个*的插入位置 begin nsk+1.si对应的整数数组； 计算第j+1项 ansi，jmaxansi，j， ansk，j-1*n； 计算状态转移方程 end；for输出最大乘积ansn，m；= 写的很好吧，要注意理解，思考，思维才会慢慢突破。P1049 最长不下降子序列 F【i】：=max（f【j】+1） j：=1.i-1；and （a【j】a【i】）；P1067 合唱队形 先分别求一个最长上升序列f【i】和一个最长下降序列g【i】，然后从1循环到n比较F【i】+g【i】-1的值，其中最大的值就是解。 这是最长不下降序列的应用，应该举一反三。P1076 数字三角形2 求最后mod100最大，似乎不具备最优子结构，不能用动态规划求解，但它可以转化为一个判定性问题，用f【I,j,k】表示到（I,j）位置时的值mod100能否得到k，若能则f为TRUE否则f为FALSE，这就可以用类似动态规划的办法求解本问题，要注意把握这种转化为判定性问题求解的方法，下面是我的程序供参考：var i,j,n,k:integer; a:array1.25,1.25of longint; f:array1.25,1.25,0.99of boolean; ff:boolean;begin readln(n); for i:=1 to n do for j:=1 to i do read(ai,j); for i:=1 to n do for j:=1 to i do for k:=0 to 99 do fi,j,k:=false; f1,1,a1,1:=tru