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

例例 13-413-4 迷宫寻宝迷宫寻宝 【问题描述】 一个 n 行 m 列的迷宫（1a then max:=b;end; Procedurework; Begin Fillchar(f,sizeof(f),0); For i:=1 tondo For j:=1 tomdo If aI,j-1 Then fI,j:=max(fi-1,j,fI,j-1)+aI,j; End; Procedure print; Begin Assign(output,fout); Rewrite(output); Writeln(fn,m); Close(output); End; Begin Init; Work; Print; End. 13-513-5 花店橱窗布置（花店橱窗布置（IOI1999IOI1999） 【问题描述】 假设你想以最美观的方式布置花店的橱窗。你有F束花，每 束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆 成一行。花瓶的位置是固定的，并从左至右，从 1 至 V 顺序编号，V 是花瓶的数目，编号为 1 的花瓶在最左边，编号为 V花瓶在最右边。 花束则可以移动，并且每束花用 1 至 F 的整数唯一标识。标识花束的 整数决定了花束在花瓶中排列的顺序，即如果 Ib then max:=a else max:=b; end; procedure work; begin fillchar(f,sizeof(f),0); f1,1:=a1,1; for i:=2 tondofi,i:=fi-1,i-1+ai,i; for i:=1 tondo for j:=i+1 to m-(n-i) do fi,j:=max(fi,j-1,fi-1,j-1+ai,j); end; begin init; work; print; end. 例例 13-613-6 机器分配机器分配 【问题描述】【问题描述】 总公司拥有高效生产设备 M 台，准备分给下属的N 个分公司。各分 公司若获得这些设备，可以为国家提供一定的盈利。 问：如何分配这 M 台设备才能使国家得到的盈利最大？求出最大 值。 其中 M=1);k 分钟 无法录制歌曲 i 但还有光盘可用 目标：fn,m,0 或 fn,m-1,t 【参考程序】【参考程序】 Vari，j，k，n，t，m：integer； a:array020 of integer; sum:integer; f:array 050, 020,060 of integer; begin assign(input,c.in); assign(output,c.out); reset(input); rewrite(output); fillchar（f,sizeof(f),0）; readln(n,t,m); for i:=1 tondo read(ai); for i:=1 tondo for j:=0 tomdo for k:=0 totdo begin fi,j,k:=fi-1,j,k; if (ai=1）and(fi,j,k=aithen fI,j,k:=max(fI,j,k,fi-1,j,k-ai+ai); if(k0)then fI,j,k:=max(fI,j,k,fi-1,j-1,w- ai+ai); end; end; procedure print; begin writeln(fn,m-1,w);/或writeln(fn,m,0) end; begin init; dp; print; end. 13-213-2 最大最大m m 子串问题子串问题 问题描述问题描述 给定由 n 个整数(可能为负整数)组成的序列 a1,a2,a3,an,以 及一个整数 m,要求确定序列 a1,a2,a3,an 得 m个不相交的子段,使 得 m 个子段的和达到最大. 输入输入 第一行:n,m.mtemp then gi,j:=temp; end; (4) 输出 writeln（f，gla,lb）; 【参考程序】 programblast； const maxn=2000； varf：text； a，b：array1maxn of byte; g:array0maxn,0maxn of longint; la,lb,i,j,k，temp：integer； c:char; begin assign(f,blast.in); reset(f); la:=0;lb:=0; while not (eoln(f) do begin read(f,c); la:=la+1; ala:=ord(c); end; readln（f） ； while not（eoln（f） ）do begin read(f,c); lb:=lb+1; blb:=ord(c); end; readln (f); readln(f,k); close(f); g0,0:=0; for i:=1 to la do gi,0:=k+gi-1,0; for j:=1 to lb do g0,j:=k+g0,j-1; for i:=1 to la do for j:=1 to lb do begin gI,j:=k+gi-1,j; temp:=k+gI,j-1; if gi,jtemp then gi,j:=temp; temp:=abs(ai-bj)+gi-1,j-1; if gi,jtemp then gi,j:=temp; end; assign(f,blast.out); rewriteln（f）; writeln(f,gla,lb)； close（f）; end. 问题描述问题描述 尼克每天上班之前都连接上因特网,接收他的上司发来的邮件,这 些邮件包含了尼克主管的部门当天要完成的全部任务,每个任务都由 一个开始时刻与一个持续时间组成. 尼克的一个工作日为 N 分钟,从第 1 分钟开始到第 N 分钟结束.当 尼克到达单位后就开始干活.如果在同一时刻有多个任务要完成,尼 克可以选择其中的任何一个来做,而其余的则有其它同事完成,反之 如果只有一个任务,则该任务则必须由尼克去完成,假如某些任务开 始时尼克正在工作,则这些任务也由尼克的同事去完成.如果某任务 于第 P 分钟开始,持续时间为 T 分钟,则该任务将在第 P+T-1 分钟结 束. 写一个程序计算尼克应该如何选取任务,才能获得最大的空暇时 间. 输入输入 输 入 数 据 第 一 行 含 两 个 用 空 格 隔 开 的 整 数 N 和 K(1minuteithen Then minutei=minutei+tj;求最大空暇时 间 J:=j-1;下一个任务 End; End; (4)输出解 Writeln(minute1); 参考程序参考程序 programprogram lignja;lignja; constconst maxnmaxn= =10000;10000; maxkmaxk= =10000;10000; varvar minuteminute: :array1maxn+1array1maxn+1 ofof integer;integer; p p : :array1maxkarray1maxk ofofinteger;integer; t:array1maxnt:array1maxn ofof integer;integer; n,n, k,k, i,i,j j : :integer;integer; f f : :text;text; beginbegin assign(f,assign(f, lignja.in);lignja.in); reset(f);reset(f); readln(f,readln(f, n,n, k);k); forfor i:=1i:=1 totok kdodo readln(f,readln(f, pi,ti);pi,ti); close(f);close(f); j:=k;j:=k; minuten+1:=0;minuten+1:=0; forfor i:=ni:=n downtodownto1 1dodo beginbegin minutei:=0;minutei:=0; ifif pjipji thenthen minutei:=1+minutei+1minutei:=1+minutei+1 elseelse whilewhile pj=ipj=i dodo beginbegin ifif minutei+tjminuteiminutei+tjminutei thenthen minutei:=minutei+tj;minutei:=minutei+tj; j:=j-1;j:=j-1; end;end; end;end; assign(f,assign(f, lignja.out);lignja.out); rewrite(f);rewrite(f); writeln(f,writeln(f, minute1);minute1); close(f);close(f); end.end. 8.48.4 书的复制书的复制 【问题描述】【问题描述】 要把 m 本有顺序的书分给 k 个人复制（抄写） ，每一个人的抄写 速度都一样，一本书不允许给两个（或以上）的人抄写，分给每个人 的书，必须是连续的，比如不能把第一，第三，第四本书给同一个人 抄写。 现在请你设计一种方案，使得复制时间最短。复制时间为抄写页 数最多的人用去的时间。 【输入】 第一行两个整数m，k； （ktthent2:=datai+1,pe-1.num else t2:=t; if t21 do begin writeln(datai,j.pos); write(datai,j.pos+1, ); i:=datai,j.pos+1; j:=j-1; end; writeln(m); end; begi