等价于两人同时走,并且走相同步数。
条件: $\Large{i+j==x+y}$
$f[i,j,x,y]$表示同时分别
从$(1,1)(1,1)$走到$(i,j)(x,y)$的路径
取数的最大值
两点$(i,j)(x,y)$的上一步可能是:
上,上:$(i-1,j)(x-1,y)$;
上,左:$(i-1,j)(x,y-1)$;
左,上:$(i,j-1)(x-1,y)$;
左,左:$(i,j-1)(x,y-1)$;
$f[i,j,x,y] = max(....)$
当$i == x$ && $j== y$时代表两条路径出现重复点
则只取一次$a[i][j]$的值
#include <iostream>
using namespace std;
const int N=11;
int a[N][N];
int f[N][N][N][N];
int main(){
int n, x, y;
cin>>n;
while(cin>>x>>y>>a[x][y], x);
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
for(int x=1; x<=n; x++)
for(int y=1; y<=n; y++)
if(i+j==x+y){
int &t=f[i][j][x][y];
t=max(max(f[i-1][j][x-1][y], f[i-1][j][x][y-1]),
max(f[i][j-1][x-1][y], f[i][j-1][x][y-1]));
if(i==x && j==y) t+=a[i][j]; //走到同一点
else t+=a[i][j]+a[x][y];
}
cout<<f[n][n][n][n];
}
// 利用约束条件,降维优化,令 i+j=x+y=k 表示走的步数
// f[k,i,x]表示共走了k步,两人分别走到i行x行,取数的最大值
#include <iostream>
#include <algorithm>
using namespace std;
const int N=11;
int a[N][N];
int f[N+N][N][N];
int main(){
int n, x, y;
cin>>n;
while(cin>>x>>y>>a[x][y], x);
for(int k=2; k<=n+n; k++) //走了k步
for(int i=1; i<=n; i++) //走到i行
for(int x=1; x<=n; x++){ //走到x行
int j=k-i, y=k-x;
if(j>=1&&j<=n&&y>=1&&y<=n){
int &t=f[k][i][x];
t=max(max(f[k-1][i-1][x-1],f[k-1][i-1][x]),
max(f[k-1][i][x-1], f[k-1][i][x]));
if(i==x) t+=a[i][j];
else t+=a[i][j]+a[x][y];
}
}
cout<<f[n+n][n][n];
}