数字三角形模型在DP中的运.doc

数字三角形模型在DP中的运用 （襄樊市第五中学　杨兵） 数字三角形（数塔）为94年IOI一道题目。题目大意： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。 对于上图中的数字三角形，从顶到底，最大的和为30。 F[i,j]表示从数字三角形顶端到第I行，第J列位置的最大和。显然有： F[i,j]=max{f[i-1,j],f[i-1,j-1]}+a[i,j] 参考程序： program p1012; var g:array[0..100,-1..100] of longint; a,ans,n,i,j:integer; function maxer(x,y:longint):longint; begin if xy then exit(x) else exit(y); end; begin readln(n); fillchar(g,sizeof(g),0); ans:=0; for i:=1 to n do begin for j:=1 to i do begin read(a); g[i,j]:=maxer(g[i-1,j],g[i-1,j-1])+a; if (i=n) and (ansg[i,j]) then ans:=g[i,j]; end; readln; end; writeln(ans); End. 定价问题 某公司考虑为某新产品定价，该产品的单位拟从每件6元、7元、8元和9元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年利润如下所示： 第一年 第二年 第三年 第四年 第五年 6元 11 11 14 22 26 7元 12 13 17 21 23 8元 15 16 17 18 17 9元 16 17 16 15 14 问如何定价，才能使公司在近五年中获取最大利润？ 分析：这道题目和数字三角形相似，无非三角形变成了矩形了。数字三角形每次只能下向和向右下走。这道题是从第一列的某一行开始向右走，每次可以向右移一格，向上或向下移一格。F[i,j]表示，第i年，第J个价格所获得最大利润，则有： F[i,j]=max{f[i-1,j-1],f[i-1,j],f[i-1,j+1]}+a[i,j] 初始时：f[0,1]=0,f[0,2]=0,f[0,3]=0,f[0,4]=0; 第1年时，f[1,1]=a[1,1]=11,f[1,2]=12,f[1,3]=15,f[1,4]=16 第2年时，f[2,1]=23,f[2,2]=28,f[2,3]=32,f[2,4]=33 第3年时，f[3,1]= ,f[3,2]= ,f[3,3]= f[3,4]= …… 第5年时，f[5,1]= ,f[5,2]= ,f[5,3]= f[5,4]= 最后结果就是max{f[5,1],f[5,2],f[5,3],f[5,4]} 代码略。 花店橱窗布置 本题为IOI’99一道题目。 问题描述 假设你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从1至V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边。花束则可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果I＜j，则花束I必须放在花束j左边的花瓶中。 例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置