信息学奥林匹克联赛培训习题与解答(附程序解析主要是动态规划)

例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]【参考程序】Constmaxn=50;maxm=50;Fin=’b1.in’;-10-1-1-1-1-12-1505-1-113-16-1-1-18910-1-1-1-1-1-1-1蓝色字体为加入的边界Fout=’b1.out’;VarF,a:array[0..maxn+1,0..maxm+1]ofinteger;I,j,k,n,m,t:integer;Procedureinit;BeginAssign(input,fin);Reset(input);Readln(n,m);Fori:=0ton+1doForj:=0tom+1doa[I,j]:=-1;A[0,1]:=0;Fori:=1tondoForj:=1tomdoBeginRead(a[I,j]);If(a[I,j-1]=-1)and(a[i-1,j]=-1)thena[I,j]:=-1;//很关键的预处理End;Close(input);End;Functionmax(a,b:integer):integer;Beginmax:=a;ifbathenmax:=b;end;Procedurework;BeginFillchar(f,sizeof(f),0);Fori:=1tondoForj:=1tomdoIfa[I,j]-1Thenf[I,j]:=max(f[i-1,j],f[I,j-1])+a[I,j];End;Procedureprint;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的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果IJ，则花束I必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即:杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶里，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。每一个花瓶的形状和颜色也不相同。因此，当每个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述的例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示:例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，是花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只需要输出其中一种摆放方式。假设条件：1≤F≤100，其中F为花束的数量，花束编号从1至F。F≤V≤100，其中V是花瓶的数量。-50≤Aij≤50，其中Aij是花束i放在花瓶j中时的美学值。【输入】第一行包含两个数：FV随后的F行中，每行包含V个整数，Aij即为输入文件中第(i+1)行中的第j个数。【输出】最大美学值。【样例输入】35723-5-2416521-41023-215-4-2020花瓶12345花束1.杜鹃花723-5-24162.秋海棠521-410233.康乃馨-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]【参考程序】programioi;varn,m,i,j:integer;a:array[1..100,1..100]ofinteger;f:array[0..100,0..100]ofinteger;procedureinit;beginreadln(n,m);fori:=1tondoforj:=1tomdoread(a[i,j]);end;procedureprint;beginwriteln(f[n,m]);end;functionmax(a,b:integer):integer;beginifabthenmax:=aelsemax:=b;end;procedurework;beginfillchar(f,sizeof(f),0);f[1,1]:=a[1,1];fori:=2tondof[i,i]:=f[i-1,i-1]+a[i,i];fori:=1tondoforj:=i+1tom-(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]ofinteger;F:array[0..maxn,0..maxm]oflongint;n,m,I,j,k:integer;procedureinit;beginassign(input,fin);reset(input);read(n,m);fori:=1tondoforj:=1tofmdoread(a[I,j]);close(input);end;functionmax(a,b:longint):longint;beginifabthenexit(a)elseexit(b);end;proceduredp;beginfillchar(f,sizeof(f),0);fori:=1tondoforj:=1tomdofork:=0tojdof[I,j]:=max(f[I,j],f[i-1,k]+a[I,j-k]);end;procedureprint;beginwriteln(f[n,m]);end;begininit;dp;print;end.例13-7制作唱片【问题描述】你刚刚继承了n首珍贵的、没有发行的歌曲，他们由流行的演唱组RauscusRockers录制。你的计划是选则其中一些歌曲来发行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]【参考程序】Vari，j，k，n，t，m：integer；a:array[0..20]ofinteger;sum:integer;f:array[0..50,0..20,0..60]ofinteger;beginassign(input,,’c.in’);assign(output,’c.out’);reset(input);rewrite(output);fillchar（f,sizeof(f),0）;readln(n,t,m);fori:=1tondoread(a[i]);fori:=1tondoforj:=0tomdofork:=0totdobeginf[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)thenf[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].状