例13-4迷宫寻宝【问题描述】一个n行m列的迷宫（1<=n,m<=5），入口在左上角，规定只能向下或向右走。
迷宫的某些地方藏有不同价值（>0）的宝藏，同时又存在一些障碍无法通过。
求到达右下角出口时收集宝藏的最大值。
【输入】第一行n和m一下n行m列描述迷宫矩阵a[I,j]（-1：障碍）；最大值【样例输入】342-150513-16-18910【样例输出】33【分析】A[I,j]保存第i行第j列的宝藏价值。
令f[I,j]为从（1，1）走到第i行第j列时所能收集的宝藏的最大价值。
状态转移方程：F[I,j]=max{f[I-1,j],f[I,j-1]}+a[I,j](i<=n,1<=m)条件：n[I,j]<>-1初始：f[1,1]=a[1,1]目标：f[n,m]【参考程序】Const maxn=50;maxm=50;Fin=’b1.in’;Fout=’b1.out’;VarF,a:array[0..maxn+1,0..maxm+1]of integer;I,j,k,n,m,t:integer;Procedure init;BeginAssign(input,fin);Reset(input);Readln(n,m);For i:=0to n+1doFor j:=0to m+1do a[I,j]:=-1;A[0,1]:=0;For i:=1to n doFor j:=1to m doBeginRead(a[I,j]);If(a[I,j-1]=-1)and(a[i-1,j]=-1)then a[I,j]:=-1;//很关键的预处理End;Close(input);End;Function max(a,b:integer):integer;Begin max:=a;if b>a then max:=b;end;Procedure work;BeginFillchar(f,sizeof(f),0);For i:=1to n doFor j:=1to m doIf a[I,j]<>-1Then f[I,j]:=max(f[i-1,j],f[I,j-1])+a[I,j];End;Procedure print;BeginAssign(output,fout);Rewrite(output);Writeln(f[n,m]);Close(output);End;BeginInit;Work;Print;End.13-5花店橱窗布置（IOI1999）【问题描述】假设你想以最美观的方式布置花店的橱窗。
你有F束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。
花瓶的位置是固定的，并从左至右，从1至V顺序编号，V 是花瓶的数目，编号为1的花瓶在最左边，编号为V花瓶在最右边。
花束则可以移动，并且每束花用1至F的整数唯一标识。
标识花束的整数决定了花束在花瓶中排列的顺序，即如果I<J，则花束I必须放在花束J左边的花瓶中。
例如，假设杜鹃花的标识数为1，秋海棠的标识为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即:杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶里，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同。
因此，当每个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。
在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示:花瓶123451.杜鹃花723-5-2416秋海棠521-41023康乃馨-215-4-2020例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。
为取得最佳美学效果，你必须在保持花束顺序的前提下，是花束的摆放取得最大的美学值。
如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需要输出其中一种摆放方式。
假设条件：1≤F≤100，其中F为花束的数量，花束编号从1至F。
F≤V≤100，其中V是花瓶的数量。
-50≤A ij≤50，其中A ij是花束i放在花瓶j中时的美学值。
【输入】第一行包含两个数：F V随后的F行中，每行包含V个整数，A ij即为输入文件中第(i+1)行中的第j个数。
【输出】最大美学值。
【样例输入】35723-5-2416521-41023-215-4-2020【样例输出】53样例说明：3束花分别一次插在2、4、5号花瓶内。
【分析】设a[i,j]为花i放入花瓶j的美学价值。
f[i,j]：前i束花放入前j个花瓶内获得的最大美学价值（花i 不一定必须插在瓶j内）。
计算f[i,j]有两种情况：(1)花i放入第j个花瓶中：f[i,j]=f[i-1,j-1]+a[i,j](2)花i不放入第j个花瓶中，只能放在前j-1个花瓶内：f[i,j]=f[i,j-1]状态转移方程：f[i,j]=max{f[i-1,j-1]+a[i,j],f[i,j-1]}初始化：f[i,i]=a[1,1]+a[2,2]+……+a[i,i]目标：f[n,m]【参考程序】program ioi;var n,m,i,j:integer;a:array[1..100,1..100]of integer;f:array[0..100,0..100]of integer;procedure init;beginreadln(n,m);for i:=1to n dofor j:=1to m do read(a[i,j]);end;procedure print;beginwriteln(f[n,m]);end;function max(a,b:integer):integer;beginif a>b then max:=a else max:=b;end;procedure work;beginfillchar(f,sizeof(f),0);f[1,1]:=a[1,1];for i:=2to n do f[i,i]:=f[i-1,i-1]+a[i,i];for i:=1to n dofor j:=i+1to m-(n-i)dof[i,j]:=max(f[i,j-1],f[i-1,j-1]+a[i,j]);end;begininit;work;print;end.例13-6机器分配【问题描述】总公司拥有高效生产设备M台，准备分给下属的N个分公司。
各分公司若获得这些设备，可以为国家提供一定的盈利。
问：如何分配这M台设备才能使国家得到的盈利最大？求出最大值。
其中M<=150，N<=100。
分配原则：每个分公司有权获得任意数目的设备，但总台数不得超过总设备数M。
【输入】第一行两个数，第一个数是分公司数N，第二个数是设备台数M。
接下来是一个N*M的矩阵A，A[I,J]是第i个公司分配j台机器所能获得的盈利。
0<=A[I,j]<=1000。
【输出】最大盈利值。
【样例输入】34101526302032384312202735【样例输出】54【分析】F[I,j]：前i个公司分配j台机器获得的最大盈利。
状态转移方程：f[[I,j]=max{f[i-1,j-k]+a[I,k]}(1<=i<=n,1<=j<=m,0<=k<=j);初始：f[1,i]:=a[1,i](1<=i<=m)目标：f[n,m]【参考程序】ConstMaxn=100;maxm=150;Fin=’work1.in’;VarA:array[0.maxn,0..maxm]of integer;F:array[0..maxn,0..maxm]of longint;n,m,I,j,k:integer;procedure init;beginassign(input,fin);reset(input);read(n,m);for i:=1to n dofor j:=1to fm doread(a[I,j]);close(input);end;function max(a,b:longint):longint;beginif a>b then exit(a)else exit(b);end;procedure dp;beginfillchar(f,sizeof(f),0);for i:=1to n dofor j:=1to m dofor k:=0to j dof[I,j]:=max(f[I,j],f[i-1,k]+a[I,j-k]); end;procedure print;beginwriteln(f[n,m]);end;begininit;dp;print;end.例13-7制作唱片【问题描述】你刚刚继承了n首珍贵的、没有发行的歌曲，他们由流行的演唱组Rauscus Rockers录制。
你的计划是选则其中一些歌曲来发行m个唱片每个唱片至多包含t分钟的音乐，唱片中的歌曲不重复。
由于你是一个古典音乐爱好者，所以你没有办法区分这些音乐的价值，你按照下面的标准进行选择：（1）这些唱片中中的歌曲必须按照它们的写作顺序进行排序。
（如果第一个唱片录制歌曲1和歌曲3，则第二个唱片从歌曲4开始选择）；（2）包含歌曲的总数尽可能多。
【输入】第一行包含数值你，n，t，m。
n<=50;t<=60;m<=20,每首歌曲的长度不超过20.第二行依次是n首歌曲的长度它们按写作的顺序排列没有一首歌曲超出唱片的长度，而且不可能将所有的歌曲都放在唱片中。
【输出】按标准选取歌曲录制，m个唱片所能录制的最多歌曲数目。
【样例输入】56443445【样例输出】4【分析】a[i]：第i首歌曲的长度；f[i,j,k]:表示第i首歌曲，用j张光盘，另加k分钟能够发行的最多歌曲数目。
容易得出：f[I,j,k]:=max{f[i-1,j,k]//不刻录第i首歌f[i-1,j,k-a[i]]+1//a[i]<=k:k分钟能够录制的歌曲if[i-1,j-1,t-a[i]]+1//(a[i]>k)and(j>=1);k分钟无法录制歌曲i但还有光盘可用}目标：f[n,m,0]或f[n,m-1,t]【参考程序】Var i，j，k，n，t，m：integer；a:array[0..20]of integer;sum:integer;f:array[0..50,0..20,0..60]of integer;beginassign(input,,’c.in’);assign(output,’c.out’);reset(input);rewrite(output);fillchar（f,sizeof(f),0）;readln(n,t,m);for i:=1to n do read(a[i]);for i:=1to n dofor j:=0to m dofor k:=0to t dobeginf[i,j,k]:=f[i-1,j,k];if(a[i]<=k)and(f[i,j,k]<f[i-1,j,k-a[i]]+1)thena[i,j,k]:=f[i-1,j,k-a[i]]+1；if（a[i]>k）and（j>=1）and(f[i,j,k]<f[i-1,j-1,t-a[i]]+1) then f[i,j,k]:=f[i-1,j-1,t-a[i]]+1;end;written(f[n,m,0])；close（intput）；close（output）；end.例13-8石子合并在一操场的南墙边摆放着N堆石子(N<=100),这N堆石子排成一排.现要将石子有序的合并成一堆.规定每次只能选相邻的两堆合并,并将新的一堆石子的数量记为该次合并的得分.编一程序,由文件读入堆数N及每堆石子数(每堆石子数<=20);选择一种合并石子的方案,使得做N-1次合并,得分的总和最少.[输入]第一行为石子堆数N.第二行为每堆石子的数量,每两个数之间用一空格隔开.[输出]合并石子后得到的最小得分.[样例输入]49445[样例输出]43[分析]设a[i]:第i堆石子的数量.f[i,j]:合并第i堆到第j堆石子得到的最小分数.Data[i,j]:第i堆到第j堆石子的总数量,则data[i,j]:=a[i]+a[i+1]+a[i+2]+..+a[j].状态转移方程:f[i,j]:=min{(f[i,k]+f[k+1,j])+data[i,j]}(i<=k<=j-1);初始值:f[i,i]=0目标:f[l,n][参考程序]constmaxn=100;vara:array[0..maxn]of integer;f:array[1..maxn,1..maxn]of longint; n,i,j,k,p:integer;procedure init;beginassign(input,'ston.in');reset(input);readln(n);a[0]:=0;for i:=1to n doread(a[i]);for i:=2to n doa[i]:=a[i-1]+a[i];close(input);end;procedure dpwork;beginfor i:=1to n do f[i,i]:=0;for p:=1to n-1dofor i:=1to n-p dobeginj:=i+p;f[i,j]:=maxlongint;for k:=i to j-1doif f[i,j]>f[i,k]+f[k+1,j]thenf[i,j]:=f[i,k]+f[k+1,j];f[i,j]:=f[i,j]+a[j]-a[i-1];end;end;procedure print;beginassign(output,'ston.out');rewrite(output);writeln(f[1,n]);close(output);end;begininit;dpwork;print;end.字符串转换问题描述设A和B是两个字符串,我们可以通过下面的三种字符操作将字符串A 转换为字符串B.字符操作包括:(1)删除一个字符.(2)插入一个字符.(3)将下一个字符改另一个字符.对于给定的字符串A和B,要求用最少的操作步数将A串转换为B串.输入第一行:A串.第二行:B串.输出将A串转换为B串所用的最少步数.样例输入ACDEFABCDE样例输出2参考程序program aa;const maxn=200;var a:array[0..maxn,0..maxn]of integer;//步数状态变量sa,sb:string;la,lb,i,j:integer;function min(a,b,c:integer):integer;//求最短步数beginmin:=a;if b<min then min:=b;if c<min then min:=c;end;beginreadln(sa);readln(sb);fillchar(a,sizeof(a),0);for i:=1to maxn do//设置边界条件begina[i,0]:=i;//删除A中的I个字符使A变成B.a[0,i]:=i;//在A中插入J个字符使A变成B.end;for i:=1to length(sa)do//枚举所有的方案for j:=1to length(sb)doif sa[i]=sb[j]then a[i,j]:=a[i-1,j-1]else a[i,j]:=min(a[i-1,j],a[i-1,j-1],a[i,j-1])+1;//删除A中最后一个字符;在A的最后插入一个字符;将A中的一个字符转换为另一个字符.write(a[i,j]);//目标end.例13-10拾金子【问题描述】古老的传说中有一个古老的游戏，游戏的名字叫拾金子。
