http://codevs.cn/problem/1043/ (题目链接)
题意
N*N的方格，每个格子中有一个数，寻找从(1,1)走到(N,N)的两条路径，使得取到的数的和最大。
Solution
水题，${f[i][j][k][l]}$表示一条路走到(i,j)，另一条路走到(k,l)，取到的最大的数。
代码
// codevs1043
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define inf 2147483640
#define MOD 10000
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=20;
int a[maxn][maxn],f[maxn][maxn][maxn][maxn],n,m; int main() {
scanf("%d",&n);
int u,v,w;
while (scanf("%d",&u)!=EOF && u) {
scanf("%d%d",&v,&w);
a[u][v]=w;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
for (int l=1;l<=n;l++) {
f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i-1][j][k][l-1]),max(f[i][j-1][k-1][l],f[i][j-1][k][l-1]))+a[i][j]+a[k][l];
if (i==k && j==l) f[i][j][k][l]-=a[i][j];
}
printf("%d",f[n][n][n][n]);
return 0;
}