题解 P1004 【方格取数】
z3475
2018-02-17 15:50:57
大家都知道走一次的动态转移方程是
f[x][y]=max(f[x-1][y],f[x][y-1])+a[x][y];
那走俩次我们可以把数组加个俩维，代表第一次最大值+第二次的最大值，那方程就变成了这个
f[x1][y1][x2][y2]=max(
f[x1-1][y1][x2-1][y2],
f[x1-1][y1][x2][y2-1],
f[x1][y1-1][x2-1][y2],
f[x1][y1-1][x2][y2-1])+a[x1][y1]+a[x2][y2];
但是按照这个方程来看，明显f[n][n][n][n]=max(...)+2a[n][n];
所以当x1==x2&&y1==y2时只要加一次
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[10][10];
int f[10][10][10][10];//记忆化
int max(int a,int b,int c,int d){
return max(max(max(a,b),c),d);
}
int po(int x1,int y1,int x2,int y2){
if (f[x1][y1][x2][y2]!=-1) return f[x1][y1][x2][y2];
if (x1<=0||y1<=0||x2<=0||y2<=0) return 0;
register int add;
if (x1==x2&&y1==y2) add=a[x1][y1];
else add=a[x1][y1]+a[x2][y2];
return f[x1][y1][x2][y2]=max(
po(x1-1,y1,x2-1,y2),
po(x1-1,y1,x2,y2-1),
po(x1,y1-1,x2-1,y2),
po(x1,y1-1,x2,y2-1)
)+add;
}
int main(){
memset(f,-1,sizeof(f));
int n;scanf("%d",&n);
int q,w,e;scanf("%d%d%d",&q,&w,&e);
do{
a[q][w]=e;
scanf("%d%d%d",&q,&w,&e);
}while(!(q==0&&w==0&&e==0));
printf("%d",po(n,n,n,n));
}
```