f[k][i1][i2]意义:在横纵坐标值的和相同时,两条路径并行得到的每条路径的最大值之和
明白了这个概念就没有难点了
两条路径分别是:
(1,1)->(i1,k-i1);
(1,1)->(i2,k-i2);
C++ 代码
#include<iostream>
#include<cstdio>
using namespace std;
const int N=109;
int f[208][N][N],a[N][N];
int main()
{
int n,x,y,w,t,j1,j2;
scanf("%d",&n);
while(~scanf("%d%d%d",&x,&y,&w)&&(x||y||w)) a[x][y]=w;
for(int k=2;k<=2*n;k++)
{
for(int i1=1;i1<=n;i1++){
j1=k-i1;
if(j1<=0)
break;
else if(j1<=n)
for(int i2=1;i2<=n;i2++){
j2=k-i2;
if(j2<=0)
break;
else if(j2<=n)
{
t=a[i1][j1];
if(i1!=i2)//一个格子只能取一次数值,取过之后变为零,所以要特判一下
{
t+=a[i2][j2];
}
f[k][i1][i2]=max(max(f[k-1][i1][i2-1],f[k-1][i1-1][i2]),f[k][i1][i2]);
f[k][i1][i2]=max(max(f[k-1][i1][i2],f[k-1][i1-1][i2-1]),f[k][i1][i2])+t;
//模拟两条路径到达对应点的情况,本质和一次路径求法f[i][j]=max(f[i][j-1],f[i-1][j])没有区别
}
}
}
}
printf("%d",f[2*n][n][n]);
return 0;
}