数字三角形模型在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 x>y 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 (ans<g[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，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须入在康乃馨左边的花瓶中，如果花瓶的数目大于花束的数目，则多余的花瓶必须空置，每个花瓶中只能放一束花。
每一个花瓶的形状和颜色也不相同。因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值（一个整数）来表示，空置花瓶的美学值为零。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用下面式样的表格来表示。

花 瓶
1
2
3
4
5
花 束
1、杜鹃花
7
23
-5
-24
16
2、秋海棠
5
21
-4
10
23
3、康乃馨
-21
5
-4
-20
20

例如，根据上表，杜鹃花放在花瓶2中，会显得非常好看；但若放在花瓶4中则显得很难看。为取得最佳美学效果，你必须在保持花束顺序的前提下，使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种，则其中任何一种摆放方式都可以接受，但你只右输出其中一种摆放方式。
假设条件（Asumption）
1≤F≤100，其中F为花束的数量，花束编号从1至F。
F≤V≤100，其中V是花瓶的数量。
-50≤Aij≤50，其中Aij 是花束i在花瓶j中时的美学值。
输入格式：
输入文件是正文文件（text file），文件名是flower.inp。
第一行包含两个数：F、V。
随后的F行中，每行包含V个整数，Aij即为输入文件中第（i+1）行中的第j个数。
输出格式：
输出文件必须是名为flower.out的正文文件，文件应包含两行：
第一行是程序所产生摆放方式的美学值。
第二行必须用F个数表示摆放方式，即该行的第K个数表示花束K所在的花瓶的编号。
输入样例：flower.inp：
3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20
flower.out：
53
2 4 5
分析：这道题显然和定价问题模型类似，也可以看成是数字三角形模型。
这道题实际上就是求从第一行某个位置I（1≤I≤V-F+1）出发，每次只能往下一格，往右K格（1≤K≤V-I-F+2）。设f[i,j]表示，前i束花放在前J个花瓶中,第i束花放在第J个花瓶的最大美学值，则显然有：F[i,j]=max{f[i-1,k]}+a[i,j]，其中i≤k<j，最后的结果应该是：max{f[F,i]}其中i=f..V。
参考代码：
program p1039;
var
a:array[1..100,1..100] of integer;
g,d:array[1..100,1..100] of longint;
i,j,f,v,k:integer;
ans:longint;
procedure print(x,y:integer); //递归输出最佳决策方案
begin
if x<>1 then print(x-1,d[x,y]);
write(y,' ');
end;
begin
readln(f,v);
for i:=1 to f do
begin
for j:=1 to v do
read(a[i,j]);
readln;
end;
fillchar(g,sizeof(g),0);
fillchar(d,sizeof(d),0);
for i:=1 to v do //初始化边界数组和记录决策
begin
g[1,i]:=a[1,i];
d[1,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 g[i,j]<g[i-1,k]+a[i,j] then
begin
g[i,j]:=g[i-1,k]+a[i,j];
d[i,j]:=k; //记录决策
end;
ans:=0;
k:=0;
for i:=f to v do
if ans<g[f,i] then begin ans:=g[f,i];k:=i; end;
writeln(ans);
print(f,k);
end.
免费馅饼（NOI’98）
一、问题描述
SERKOI最新推出了一种叫做“免费馅饼”的游戏。
游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘（如图一）。

图一
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。
输入格式：
输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度W（1~99之间的奇数）和高度H（1 ~ 100之间的整数）。
接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0 ~ 1000秒），水平位置、下落速度（1 ~ 100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。
输出格式：
输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。
其后的每一行依时间顺序给出了游戏者每秒的决策。输出0表示原地不动。1或2表示向右移动一步或两步、-1或-2表示向坐移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止。
输入样例：
3 3
0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4
输出样例：
12
-1
1
1
分析：
如果我们把第0秒，第1秒，第2秒，…，第maxtime秒末落入第H行的格子的得分都求出来，问题就变成了从第0秒所在的中间那个位置，可以经过五种选择（-2,-1,0,1,2）将状态转移到第1秒末，第1秒又可经过5种选择将状态转移到第2秒，依此类推，直到所有的走到最大的时间maxtime。这个模型就是我们所熟悉的从一个矩形中间位置，可以按照（-2,-1,0,1,2）这几中走法，走到矩形的最底层，找一个最大的和的路径。
现在问题变成，怎样把这个矩阵建立起来，怎样求最大的时间maxtime等问题。Maxtime很好求，我们可以求出所有时刻和这个时刻落下这个馅饼到第H行需要的时间之和的最大值就是maxtime,另外“当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼”这说明了，（H-1）% SPEED必须等于0，即必须整除，否则也收不了这个馅饼。明白这两个问题之后，问题迎刃而解了。
设f[i,j]表示在第I秒末，在J格时的最大得分，其中I=0，1，2，…，maxtime，j=1,2,…,
W。显然，有状态转移方程f[i,j]=max{f[i-1,j-k]},其中k=-2,-1,0,1,2,can[i-1,j-k]必须可以到达。
最后所求显然是max{f[maxtime,i]}其中i=1,2,…,w。边界条件显然f[0,i]=0其中i=1,2,…,w。Can[0,(w+1) div 2]=true。
参考代码：
program p1016;
var
d,map,g:array[0..1000,1..99] of longint;
can:array[0..1000,1..99] of boolean;
ans,i,j,k,w,h,t,posi,speed,mark,maxtime:integer;
procedure print(x,y:integer); //输出最优方案
begin
if x>1 then print(x-1,y-d[x,y]);
writeln(d[x,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 speed>0 then continue;//不能在某1秒末到达游戏者所在格子，下一个。
if maxtime<(t+(h-1) div speed) then maxtime:=t+(h-1) div speed;//找最大maxtime
map[t+(h-1) div speed,posi]:=map[t+(h-1) div speed,posi]+mark;//把相应时刻得分累加
end;
can[0,(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 (can[i-1,j-k]=true) and (g[i,j]<g[i-1,j-k]+map[i,j])//最佳方案，并记录
then begin
g[i,j]:=g[i-1,j-k]+map[i,j];
d[i,j]:=k;
can[i,j]:=true;
end;
if (can[i,j]=false) and (can[i-1,j-k]=true) then begin can[i,j]:=true;d[i,j]:=k; end;//这一步不能省略，如果某一时刻没有饼子落下，不能说这个时刻的位置就无法达到，他仍然可以到达该位置，为了下一个时刻的更好决策。比如第0秒末和第1秒末可能没有饼子落下，如果人不动的话，可能第3秒末的更好的决策就无法得到了。或者因为第0,第1秒末都不可达，后面的就无法接饼子了。这一步很重要。
end;
ans:=0;k:=0;
for i:=1 to w do
if ans<g[maxtime,i] then begin ans:=g[maxtime,i];k:=i;end;
writeln(ans);
if ans<>0 then print(maxtime,k);
End.
方格取数
问题描述：
　　设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：

　　某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字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
简单分析：有些同学可能认为，走两次数字三角形，样例可以过，但无法通过所有的测试数据。第一次取的显然是最大值，但第二次取的未必次大，所以也许两条非最大的路，也许比一条最大一条小一点的路更优。设计一个状态opt[i1,j1,i2,j2]表示两条路分别走到（i1,j1）点和（i2,j2）点时取到的最大值。显然决策有4种（乘法原理一个点两种*另一个点的两种）即（上，上）（上，左）（左，上）（左，左）上和左表示从哪个方向走到该点，当然要注意走到同行，同列，同点时的情况（因为要求路径不重复）。
状态转移方程：
max{opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2]}+a[i1,j1]+a[i2,j2]
(其中1<=i1=i2<=n,1<=j1<=j2<=n)
max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])
(其中1<=j1=j2<=n,1<=i1<=i2<=n)
opt[i,j]= max{opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],
opt[i1,j1-1,i2,j2-2]}+a[i1,j1]+a[i2,j2] (1<=i1,j1<=i2,j2<=n)
时间复杂度：状态数O（N4）*转移代价O（1）=总复杂度O（N4）
空间复杂度：O（N4）
　　由于数据很小所以这样做虽然时间和空间复杂度都很高但还是可以AC的。如果这个题的数据范围在大点就得优化了，怎么优化这个程序呢？上面说过对于时间空间都大的时候，首先想到的就是寻找特点，改变状态的表示法，减少状态的维数。
仔细分析我们发现，处于同行，同列的状态，等价于另外一个点在对角线上的状态。而这条对角线正是此题的阶段。因为在状态转移的时候后面的哪个点总是从固定的一个方向转移来的。也就是说我们只要对角先上的状态就可以省掉那些同行同列的状态了。做过N皇的同学一定知道怎么表示右上到左下的这几条对角线，不知道的同学也没关系,对于一个点（i,j）他对角右上角的点就是（i-1，j+1）所以可以看出这些点的和是定值，且值从2到N*2。这样用三个变量就可以表示这两个点了，于是设计状态opt[k,i1,i2]表示处于阶段K时走到i1,i2的两条路径所取得的数的最大和。

　　用上面的思维不难想出动态转移方程：
Max{opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],
　　　　opt[k-1,i1,i2])}+a[i1,k-i1]+a[i2,k-i2](1<=i1,i2<=n,2<=k<=n*2,i1<>i2)
otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,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
一行，表示最大的总和。
样例输入
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
样例输出
39
时间限制 Time Limitation
各个测试点1s