链接：Luogu-P1004
思路
考虑换成两次都从(0,0)出发 ，向右/下行走。 显然两者到达终点时走过的步数相同。 因此可以让二者每次都走一步，分4种情况讨论。 注意由于步数相同不可能二者位于同一列上下相邻两格。 于是唯一的特殊情况就是二者处于同一个格子，这时这个格子的数只能取一次。 特判处理即可。 状态：$ f[x_1][y_1][x_2][y_2] $：位于 $(x_1,y_1)$ 和 $(x_2,y_2)$，而且拿了这两个点的数后行走所获得的最大数字和。 复杂度为 $ O(n^4) $ ，由于 $ n \leq 9 $，可以接受 。
代码
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN = 9;
const int dx[] = {0,1} ,dy[] = {1,0};
int N,A[MAXN+5][MAXN+5],Opt[MAXN+5][MAXN+5][MAXN+5][MAXN+5];
int main(){
int tx,ty,tv;
scanf("%d",&N);
while(scanf("%d %d %d",&tx,&ty,&tv) && tx && ty && tv)
A[tx][ty]=tv;
for(int x1=N;x1>=1;x1--)
for(int y1=N;y1>=1;y1--)
for(int x2=N;x2>=1;x2--)
for(int y2=N;y2>=1;y2--)
if(x1+y1 == x2+y2) //Valid
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
{
int nx1=x1+dx[j],ny1=y1+dy[j],
nx2=x2+dx[k],ny2=y2+dy[k];
int t=A[x1][y1]+A[x2][y2]
-A[x1][y1]*(x1==x2 && y1==y2)+Opt[nx1][ny1][nx2][ny2];
Opt[x1][y1][x2][y2]=max(Opt[x1][y1][x2][y2],t);
}
printf("%d\n",Opt[1][1][1][1]);
}
