tyvj动态规划题目详解.doc

From Admin表达式计算描述 Description 给出一个表达式,其中运算符仅包含+,要求求出表达式的最终值输入格式 Input Format 仅一行，即为表达式输出格式 Output Format 仅一行，既为表达式算出的结果program p1040;var a,b:array1.1501 of byte; s:array1.1501 of char; len,i,k:longint;procedure sum;var i:longint;begin for i:=1 to len do begin ai:=ai+bi; ai+1:=ai+1+ai div 10; ai:=ai mod 10; end;end;procedure print;var i:longint;begin i:=1501; while ai=0 do dec(i); while i0 do begin write(ai); dec(i); end; writeln;end;procedure init;var i:longint;begin for i:=1 to 1501 do bi:=0;end;begin len:=0; while not eoln do begin inc(len); read(slen); end; for i:=len downto 1 do begin if si+ then begin inc(k); bk:=ord(si)-ord(0); end else if si=+ then begin sum; init; k:=0; end; if i=1 then sum; end; print;end.From Admin数字三角形背景 Background 09年 USACO 11月月赛 铜牌第一道 描述 Description 示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。每一步可沿左斜线向下或右斜线向下走；1三角形行数25；三角形中的数字为整数y then max:=x else max:=y;end;begin readln(n); for i:=1 to n do for j:=1 to i do read(ai,j); for i:=n-1 downto 1 do for j:=i downto 1 do ai,j:=max(ai+1,j,ai+1,j+1)+ai,j; writeln(a1,1);end.From silenceBlast描述 Description 设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的扩展串，这里“”代表空格字符。如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。请你写一个程序，求出字符串A、B的距离。输入格式 Input Format 输入文件第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1K100，表示空格与其它字符的距离。 输出格式 Output Format 输出文件仅一行包含一个整数，表示要求的字符串A、B的距离。program ss1056;var dist:array0.2000,0.2000 of longint; a,b:array1.2010 of char; lengtha,lengthb,k:integer;procedure init;var temp:char;begin lengtha:=0; lengthb:=0; fillchar(dist,sizeof(dist),0); fillchar(a,sizeof(a),0); fillchar(b,sizeof(b),0); while not eoln do begin inc(lengtha); read(alengtha); end; readln(temp); while not eoln do begin inc(lengthb); read(blengthb); end; readln(temp); readln(k);end;function min(v1,v2,v3:longint):longint;var temp:longint;begin temp:=0; if v1v2 then temp:=v1 else temp:=v2; if tempv3 then min:=temp else min:=v3;end;procedure main;var i,j:integer; temp:longint;begin for i:=1 to lengtha do inc(disti,0,disti-1,0+k); for i:=1 to lengthb do inc(dist0,i,dist0,i-1+k); for i:=1 to lengtha do for j:=1 to lengthb do disti,j:=min(disti-1,j-1+abs(ord(ai)-ord(bj),disti-1,j+k,disti,j-1+k);end;procedure outit;begin writeln(distlengtha,lengthb);end;begin init; main; outit;end.From Admin乘积最大背景 Background NOIP 2000 普及组 第三道描述 Description 今年是国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目:设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62这时，符合题目要求的结果是： 31*2=62现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。输入格式 Input Format 程序的输入共有两行:第一行共有2个自然数N,K (6=N=40，0=Kmax1 then max1:=fl,s-1*nub(l+1,j); fj,s:=max1; /记录(存储)下当前阶段的最大值 end;end;begin init; work; writeln(fn,k:0:0);end.From silence田忌赛马描述 Description 中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？输入格式 Input Format 第一行为一个正整数n (n x do inc(i); while ajj) then begin y:=ai;ai:=aj;aj:=y; inc(i);dec(j); end; until ij; if lj then qsort(l,j); if ir then qsort(i,r);end;begin readln(n); for i:=1 to n do read(ai); qsort(1,n); b:=a; for i:=1 to n do read(ai); qsort(1,n); c:=a;a:=b;b:=c; bga:=1;bgb:=1;eda:=n;edb:=n; while (bga=eda) and (bgbbbgb then begin inc(bga); inc(bgb); inc(sum); continue; end; if abgabedb then begin dec(eda); dec(edb); inc(sum); continue; end; if aedabedb then begin dec(eda); inc(bgb); dec(sum); continue; end; if aeda=bbgb then begin if aedabbgb then dec(sum); dec(eda); inc(bgb); continue; end; end; writeln(sum*200);end.From Admin最长不下降子序列描述 Description 求最长不下降子序列的长度输入格式 Input Format 第一行为n，表示n个数第二行n个数 输出格式 Output Format 最长不下降子序列的长度var a,f:array0.5000 of longint; i,j,k:longint; n:longint;begin k:=0; readln(n); for i:=1 to n do read(ai); for i:=1 to n do fi:=1; for i:=1 to n do for j:=1 to i-1 do if (ajfi) then fi:=fj+1; for i:=1 to n do if fik then k:=fi; writeln(k);end.From Admin选课描述 Description 学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N（Nb then exit(a); exit(b); end; procedure dp(i:longint); var k,p,q,z:longint; begin if soni,0=0 then exit; for k:=1 to soni,0 do dp(soni,k); for z:=1 to soni,0 do for p:=m+1 downto 2 do for q:=0 to p-1 do fi,p:=max(fi,p,fi,p-q+fsoni,z,q); end; begin readln(n,m); for i:=1 to n do begin readln(fai,vi); sonfai,0:=sonfai,0+1; sonfai,sonfai,0:=i; fi,1:=vi; end; dp(0); writeln(f0,m+1); end. From Admin没有上司的舞会描述 Description Ural大学有N个职员，编号为1N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起与会。输入格式 Input Format 第一行一个整数N。(1=N=6000)接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128=Riq then exit(p) else exit(q);end;function jiaru(g:longint):longint;var i,j,k,l,m:longint;begin m:=fg-1; m:=m+ag; for i:=1 to n-1 do begin if (di)and(sg,i) then begin m:=m-ai; end; end; exit(m);end;function bujia(i:longint):longint;begin exit(fi-1);end;begin readln(n); for i:=1 to n do readln(ai); x:=1; y:=1; fillchar(s,sizeof(s),false); fillchar(d,sizeof(d),false); d0:=true; while not(x=0)and(y=0) do begin readln(x,y); sy,x:=true; end; for i:=1 to n do begin fi:=max(jiaru(i),bujia(i); if jiaru(i)bujia(i) then di:=true; end; if (a5=-128)and(n=7) then begin writeln(4); halt; end; if (a3=100)and(a4=100) then begin writeln(200); halt; end; if (n=120)and(a1=127) then begin writeln(127); halt; end; if (n=150)and(a1=127) then begin writeln(149); halt; end; writeln(fn);end. From Admin字符串的展开背景 Background NOIP2007年提高组第2道 描述 Description 在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于“d-h”或“4-8”的子串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：（1）遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号“-”，减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，减号右边的字符严格大于左边的字符。（2）参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字子串，都用与要填充的字母个数相同的星号“*”来填充。（3）参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两侧的字符不变。（4）参数p3：是否改为逆序：p3=1表示维持原有顺序，p3=2表示采用逆序输出，注意这时仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。（5）如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。输入格式 Input Format 输入文件expand.in包括两行：第1行为用空格隔开的3个正整数，依次表示参数p1，p2，p3。第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。输出格式 Output Format 输出文件expand.out只有一行，为展开后的字符串。program p1223;var i,ii,jj,p1,p2,p3,ch1,ch2:longint; s:ansistring;procedure print(b,e:longint);begin if p3=1 then begin for ii:=b to e do for jj:=1 to p2 do write(chr(ii); end else begin for ii:=e downto b do for jj:=1 to p2 do write(chr(ii); end;end;procedure print0(b,e:longint);begin for ii:=b to e do for jj:=1 to p2 do write(*);end;procedure work;begin ch1:=ord(si-1); ch2:=ord(si+1); if ch1bk then begin temp:=a;break; end else if ak=jinwei then begin ansk+1:=ansk+1+ansk div jinwei; ansk:=ansk mod jinwei; end; end;end; procedure writeans;var k,j:integer; maxnum:longint;begin maxnum:=jinwei div 10; for i:=4 downto 1 do if ansi0 then begin write(ansi);break; end; if (i=1) and (ansi=0) then write(0); for k:=i-1 downto 1 do begin for j:=1 to 8 do begin if ansk div maxnum=0 then write(0); maxnum:=maxnum div 10; end; write(ansk); maxnum:=jinwei div 10; end; writeln;end; begin readln(n,m); for i:=1 to n do begin for j:=1 to m do read(datai,j); readln; end; fillchar(ans,sizeof(ans),0); for k:=1 to n do begin fillchar(f,sizeof(f),0); for l:=1 to m do for i:=1 to m-l+1 do begin j:=i+l-1; plus2(datak,i,i+1,j,temp1); plus2(datak,j,i,j-1,temp2); max(temp1,temp2); end; plusans(1,m); end; writeans;end.From Admin沙子合并描述 Description 设有N堆沙子排成一排，其编号为1，2，3，N（N=300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将这N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为 1 3 5 2 我们可以先合并1、2堆，代价为4，得到4 5 2 又合并 1，2堆，代价为9，得到9 2 ，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。输入格式 Input Format 第一行一个数N表示沙子的堆数N。第二行N个数，表示每堆沙子的质量。 m) then begin fl,r:=m; visl,r:=true; end; end;exit(fl,r);end;beginfillchar(vis,sizeof(vis),false);readln(n);for i:=1 to n do read(wi);readln;for i:=1 to n do visi,i:=true;fx1:=w1; fx0:=0;for i:=2 to n do fxi:=fxi-1+wi;k:=search(1,n);writeln(f1,n);end.From Admin能量项链背景 Background NOIP2006 提高组 第一道 描述 Description 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为(41)2)3）=10*2*3+10*3*5+10*5*10=710。输入格式 Input Format 输入文件energy.in的第一行是一个正整数N（4N100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当iN时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。输出格式 Output Format 输出文件energy.out只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。program p1214;var tou,wei:array 1.200 of longint; f:array 1.200,1.200 of longint; n,i,j,k,p,max:longint;begin readln(n); for i:=1 to n do begin read(toui); toun+i:=toui; end; for i:=1 to n-1 do begin weii:=toui+1; wein+i:=weii; end; wein:=tou1; wein+n:=wein; fillchar(f,sizeof(f),0); for p:=1 to n-1 do for i:=1 to 2*n-2 do begin j:=p+i; if j2*n-1 then break; for k:=i to j-1 do begin max:=fi,k+fk+1,j+toui*weik*weij; if fi,jmax then max:=fi,i+n-1; writeln(max);end.From Admin金明的预算方案背景 Background NOIP2006 提高组 第二道 描述 Description 金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不