《数字三角形模型在DP中的运用.doc》由会员分享，可在线阅读，更多相关《数字三角形模型在DP中的运用.doc（9页珍藏版）》请在三一办公上搜索。
1、数字三角形模型在DP中的运用（襄樊市第五中学杨兵）数字三角形（数塔）为94年IOI一道题目。题目大意： 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。 对于上图中的数字三角形，从顶到底，最大的和为30。Fi,j表示从数字三角形顶端到第I行，第J列位置的最大和。显然有： Fi,j=maxfi-1,j,fi-1,j-1+ai,j参考程序：program p101
2、2; var g:array0.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); gi,j:=maxer(gi-1,j,gi-1,j-1)+a; if (i=n) and (ansgi,j)
3、 then ans:=gi,j; end; readln; end; writeln(ans); End.定价问题某公司考虑为某新产品定价，该产品的单位拟从每件6元、7元、8元和9元这四个中选取一个，每年允许价格有1元幅度的变动，该产品预计畅销五年，据预测不同价格下各年利润如下所示：第一年第二年第三年第四年第五年6元11111422267元12131721238元15161718179元1617161514问如何定价，才能使公司在近五年中获取最大利润？分析：这道题目和数字三角形相似，无非三角形变成了矩形了。数字三角形每次只能下向和向右下走。这道题是从第一列的某一行开始向右走，每次可以向右移一格
4、，向上或向下移一格。Fi,j表示，第i年，第J个价格所获得最大利润，则有：Fi,j=maxfi-1,j-1,fi-1,j,fi-1,j+1+ai,j初始时：f0,1=0,f0,2=0,f0,3=0,f0,4=0;第1年时，f1,1=a1,1=11,f1,2=12,f1,3=15,f1,4=16第2年时，f2,1=23,f2,2=28,f2,3=32,f2,4=33第3年时，f3,1= ,f3,2= ,f3,3= f3,4=第5年时，f5,1= ,f5,2= ,f5,3= f5,4=最后结果就是maxf5,1,f5,2,f5,3,f5,4代码略。花店橱窗布置本题为IOI99一道题目。问题描述 假
5、设你想以最美观的方式布置花店的橱窗。你有F束花，每束花的品种都不一样，同时，你至少有同样数量的花瓶，被按顺序摆成一行。花瓶的位置是固定的，并从左至右，从1至V顺序编号，V是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边。花束则可以移动，并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序，即如果Ij，则花束I必须放在花束j左边的花瓶中。 例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余
6、的花瓶必须空置，每个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示。花 瓶12345花 束1、杜鹃花723-5-24162、秋海棠521-410233、康乃馨-215-4-2020 例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都
7、可以接受，但你只右输出其中一种摆放方式。假设条件（Asumption）1F100，其中F为花束的数量，花束编号从1至F。FV100，其中V是花瓶的数量。-50Aij50，其中Aij 是花束i在花瓶j中时的美学值。输入格式： 输入文件是正文文件（text file），文件名是flower.inp。 第一行包含两个数：F、V。 随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数。输出格式： 输出文件必须是名为flower.out的正文文件，文件应包含两行： 第一行是程序所产生摆放方式的美学值。 第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。
8、输入样例：flower.inp： 3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20flower.out： 53 2 4 5分析：这道题显然和定价问题模型类似，也可以看成是数字三角形模型。这道题实际上就是求从第一行某个位置I（1IV-F+1）出发，每次只能往下一格，往右K格（1KV-I-F+2）。设fi,j表示，前i束花放在前J个花瓶中,第i束花放在第J个花瓶的最大美学值，则显然有：Fi,j=maxfi-1,k+ai,j，其中ikj，最后的结果应该是：maxfF,i其中i=f.V。参考代码：program p1039; var a:array1.1
9、00,1.100 of integer; g,d:array1.100,1.100 of longint; i,j,f,v,k:integer; ans:longint; procedure print(x,y:integer); /递归输出最佳决策方案 begin if x1 then print(x-1,dx,y); write(y, ); end; begin readln(f,v); for i:=1 to f do begin for j:=1 to v do read(ai,j); readln; end; fillchar(g,sizeof(g),0); fillchar(d,s
10、izeof(d),0); for i:=1 to v do /初始化边界数组和记录决策 begin g1,i:=a1,i; d1,i:=i; end; for i:=2 to f do /以花束为阶段，枚举阶段 for j:=i to v-f+i do /枚举第i束花，可能放的花瓶位置，即枚举状态 for k:=i-1 to j-1 do /枚举决策，第i-1束花可能放的位置。 if gi,jgi-1,k+ai,j then begin gi,j:=gi-1,k+ai,j; di,j:=k; /记录决策 end; ans:=0; k:=0; for i:=f to v do if ans1 t
11、hen print(x-1,y-dx,y); writeln(dx,y); end; begin readln(w,h); maxtime:=0; fillchar(map,sizeof(map),0);/存得分表，就是那个矩阵 fillchar(can,sizeof(can),0);/用来记录该时刻这个位置的饼子是不是能接到fillchar(g,sizeof(g),false);/最大得分Fillchar(d,sizeof(d),0);/用来记录最优决策 while not eof() do begin readln(t,posi,speed,mark); if (h-1) mod spee
12、d0 then continue;/不能在某1秒末到达游戏者所在格子，下一个。 if maxtime(t+(h-1) div speed) then maxtime:=t+(h-1) div speed;/找最大maxtime mapt+(h-1) div speed,posi:=mapt+(h-1) div speed,posi+mark;/把相应时刻得分累加 end; can0,(w+1) div 2:=true; for i:=1 to maxtime do/枚举阶段 for j:=1 to w do/枚举状态 for k:=2 downto -2 do/枚举可能的决策 begin if
13、 (cani-1,j-k=true) and (gi,jgi-1,j-k+mapi,j)/最佳方案，并记录 then begin gi,j:=gi-1,j-k+mapi,j; di,j:=k; cani,j:=true; end; if (cani,j=false) and (cani-1,j-k=true) then begin cani,j:=true;di,j:=k; end;/这一步不能省略，如果某一时刻没有饼子落下，不能说这个时刻的位置就无法达到，他仍然可以到达该位置，为了下一个时刻的更好决策。比如第0秒末和第1秒末可能没有饼子落下，如果人不动的话，可能第3秒末的更好的决策就无法得到
14、了。或者因为第0,第1秒末都不可达，后面的就无法接饼子了。这一步很重要。 end; ans:=0;k:=0; for i:=1 to w do if ansgmaxtime,i then begin ans:=gmaxtime,i;k:=i;end; writeln(ans); if ans0 then print(maxtime,k); End.方格取数问题描述：设有N*N的方格图(N=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）： 某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（
15、取走后的方格中将变为数字0）。 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。输入格式：输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。输出格式：只需输出一个整数，表示2条路径上取得的最大的和。输入样例： 8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0样例输出：67简单分析：有些同学可能认为，走两次数字三角形，样例可以过，但无法通过所有的测试数据。第一次取的显然是最大值，但第二次取的未必次大，所以也许
16、两条非最大的路，也许比一条最大一条小一点的路更优。设计一个状态opti1,j1,i2,j2表示两条路分别走到（i1,j1）点和（i2,j2）点时取到的最大值。显然决策有4种（乘法原理一个点两种*另一个点的两种）即（上，上）（上，左）（左，上）（左，左）上和左表示从哪个方向走到该点，当然要注意走到同行，同列，同点时的情况（因为要求路径不重复）。状态转移方程：maxopti1-1,j1,i2-1,j2,opti1,j1-1,i2-1,j2+ai1,j1+ai2,j2(其中1=i1=i2=n,1=j1=j2=n) max(opti1-1,j1,i2,j2-1,opti1,j1-1,i2,j2-1)(
17、其中1=j1=j2=n,1=i1=i2=n)opti,j= maxopti1-1,j1,i2-1,j2,opti1-1,j1,i2,j2-1,opti1,j1-1,i2-1,j2,opti1,j1-1,i2,j2-2+ai1,j1+ai2,j2 (1=i1,j1=i2,j2=n)时间复杂度：状态数O（N4）*转移代价O（1）=总复杂度O（N4）空间复杂度：O（N4）由于数据很小所以这样做虽然时间和空间复杂度都很高但还是可以AC的。如果这个题的数据范围在大点就得优化了，怎么优化这个程序呢？上面说过对于时间空间都大的时候，首先想到的就是寻找特点，改变状态的表示法，减少状态的维数。仔细分析我们发现，
18、处于同行，同列的状态，等价于另外一个点在对角线上的状态。而这条对角线正是此题的阶段。因为在状态转移的时候后面的哪个点总是从固定的一个方向转移来的。也就是说我们只要对角先上的状态就可以省掉那些同行同列的状态了。做过N皇的同学一定知道怎么表示右上到左下的这几条对角线，不知道的同学也没关系,对于一个点（i,j）他对角右上角的点就是（i-1，j+1）所以可以看出这些点的和是定值，且值从2到N*2。这样用三个变量就可以表示这两个点了，于是设计状态optk,i1,i2表示处于阶段K时走到i1,i2的两条路径所取得的数的最大和。用上面的思维不难想出动态转移方程： Maxoptk-1,i1-1,i2-1,op
19、tk-1,i1-1,i2,optk-1,i1,i2-1,optk-1,i1,i2)+ai1,k-i1+ai2,k-i2(1=i1,i2=n,2=k=n*2,i1i2)otpk,i1,i2=optk-1,i1-1,i2+ai1,k-i1(1=i1,i2=n,2=k=n*2,i1=i2)三取方格数背景 Background JerryZhou同学经常改编习题给自己做。这天，他又改编了一题。描述 Description 设有N*N的方格图，我们将其中的某些方格填入正整数，而其他的方格中放入0。某人从图的左上角出发，可以向下走，也可以向右走，直到到达右下角。在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。 输入格式 Input Format 第一行:N(4=N=20)接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0输出格式 Output Format 一行，表示最大的总和。样例输入 41 2 3 42 1 3 41 2 3 41 3 2 4样例输出39时间限制 Time Limitation 各个测试点1s
