题目
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:
2.gif
某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
题目分析
这题从一开始时一个劲的瞪,愣是没想出方法,看了y总的视频也没想出方法,最后还是看了某位同村的题解才恍然大悟
首先这题是摘花生的扩展题,如果用走一遍再走一遍的方法,得到的受第一次局部最优的影响下的全局最优解
所以不如将题目理解为两个小孩一起摘花生,每次走的步数一样,下面直接引用别的同学的书法
- k =i1+j1=i2+j2k=i1+j1=i2+j2: 两个小朋友同时走, 每个人走的步数和是一样的.
- f[i1,j1,i2,j2]f[i1,j1,i2,j2]: 由摘花生问题可以推广出从(1,1),(1,1)(1,1),(1,1)走到(i1,j1),(i2,j2)(i1,j1),(i2,j2)能获得的最大花生数目.
- 由上面的两条性质可以推出三维的状态转移方程f[i1,k−i1,i2,k−i2]→f[k,i1,i2]f[i1,k−i1,i2,k−i2]→f[k,i1,i2]:两个小朋友同时走kk步,从(1,1),(1,1)(1,1),(1,1)走到(i1,j1),(i2,j2)(i1,j1),(i2,j2)能获得的最大花生数目.
- 0:代表小朋友要到下边一个格子
- 1:代表小朋友要到右边一个格子
- 难点:∀∀格子仅能取一次. 两个小朋友在同一个格子→→必有i1==i2,j1==j2i1==i2,j1==j2,而后边状态限制同时走,所以当i1==i2i1==i2时便走到同一格.
闫式dp大法
状态表示
f[k][i1][i2]
- 集合:从(1,1)分别到(i1,j1)和(i2,j2)的所有路径
- 属性:两条路径和的最大值
状态转移
一条路劲可以从上方或者左方转移过来,所以两条路径就有四种
1. 从左方和左方 f[k-1][i1][i2]
2. 从上方和上方 f[k-1][i1-1][i2-1]
3. 从左方和上方 f[k-1][i1][i2-1]
4. 从上方和左方 f[k-1][i1-1][i2]
C++ 代码
#include<iostream>
using namespace std;
const int N=15;
int a[N][N];
int f[2*N][N][N];
int b[N][N];
int main()
{
int n,x,y,c;
cin>>n;
while(cin>>x>>y>>c,x&&y&&c)
{
a[x][y]=c;
}
int i1,i2,j1,j2;
for(int k=2;k<=n*2;k++)
{
for(int i1=1;i1<=n;i1++)
{
for(int i2=1;i2<=n;i2++)
{
//因为k固定,所以可以推算出j1和j2
j1=k-i1,j2=k-i2;
//判断j1,j是否2合法
if(j1<=n&&j1>=1&&j2<=n&&j2>=1)
{
int t=a[i1][j1];
//如果不重复则再加意义权重
if(i1!=i2) t+=a[i2][j2];
//保留最大值
f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+t);
f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t);
f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+t);
f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+t);
}
}
}
}
cout<<f[2*n][n][n]<<endl;
return 0;
}