信息學(xué)奧林匹克聯(lián)賽培訓(xùn)習(xí)題與解答附程序解析主要是動態(tài)規(guī)劃.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） 【問題描述】 假設(shè)你想以最美觀的方式布置花店的櫥窗。你有F束花，每 束花的品種都不一樣，同時，你至少有同樣數(shù)量的花瓶，被按順序擺 成一行?；ㄆ康奈恢檬枪潭ǖ模淖笾劣?，從 1 至 V 順序編號，V 是花瓶的數(shù)目，編號為 1 的花瓶在最左邊，編號為 V花瓶在最右邊。 花束則可以移動，并且每束花用 1 至 F 的整數(shù)唯一標(biāo)識。標(biāo)識花束的 整數(shù)決定了花束在花瓶中排列的順序，即如果 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 機(jī)器分配機(jī)器分配 【問題描述】【問題描述】 總公司擁有高效生產(chǎn)設(shè)備 M 臺，準(zhǔn)備分給下屬的N 個分公司。各分 公司若獲得這些設(shè)備，可以為國家提供一定的盈利。 問：如何分配這 M 臺設(shè)備才能使國家得到的盈利最大？求出最大 值。 其中 M=1);k 分鐘 無法錄制歌曲 i 但還有光盤可用 目標(biāo)：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 個整數(shù)(可能為負(fù)整數(shù))組成的序列 a1,a2,a3,an,以 及一個整數(shù) m,要求確定序列 a1,a2,a3,an 得 m個不相交的子段,使 得 m 個子段的和達(dá)到最大. 輸入輸入 第一行: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. 問題描述問題描述 尼克每天上班之前都連接上因特網(wǎng),接收他的上司發(fā)來的郵件,這 些郵件包含了尼克主管的部門當(dāng)天要完成的全部任務(wù),每個任務(wù)都由 一個開始時刻與一個持續(xù)時間組成. 尼克的一個工作日為 N 分鐘,從第 1 分鐘開始到第 N 分鐘結(jié)束.當(dāng) 尼克到達(dá)單位后就開始干活.如果在同一時刻有多個任務(wù)要完成,尼 克可以選擇其中的任何一個來做,而其余的則有其它同事完成,反之 如果只有一個任務(wù),則該任務(wù)則必須由尼克去完成,假如某些任務(wù)開 始時尼克正在工作,則這些任務(wù)也由尼克的同事去完成.如果某任務(wù) 于第 P 分鐘開始,持續(xù)時間為 T 分鐘,則該任務(wù)將在第 P+T-1 分鐘結(jié) 束. 寫一個程序計算尼克應(yīng)該如何選取任務(wù),才能獲得最大的空暇時 間. 輸入輸入 輸 入 數(shù) 據(jù) 第 一 行 含 兩 個 用 空 格 隔 開 的 整 數(shù) N 和 K(1minuteithen Then minutei=minutei+tj;求最大空暇時 間 J:=j-1;下一個任務(wù) 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 書的復(fù)制書的復(fù)制 【問題描述】【問題描述】 要把 m 本有順序的書分給 k 個人復(fù)制（抄寫） ，每一個人的抄寫 速度都一樣，一本書不允許給兩個（或以上）的人抄寫，分給每個人 的書，必須是連續(xù)的，比如不能把第一，第三，第四本書給同一個人 抄寫。 現(xiàn)在請你設(shè)計一種方案，使得復(fù)制時間最短。復(fù)制時間為抄寫頁 數(shù)最多的人用去的時間。 【輸入】 第一行兩個整數(shù)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