Description
【题目背景】
JerryZhou同学经常改编习题给自己做。
这天，他又改编了一题。。。。。
【问题描述】
设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
Input
第一行:N (4<=N<=20).
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0.
Output
一行，表示最大的总和。
Sample Input
4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4
Sample Output
39
分析：
以对角线为状态，则可以将维数压缩至4维，因为每一个状态k=x+y-1;而状态k最多是2*n个。
状态方程：F[k][i1][i1][i3]表示第k个状态在横左边为(i1,i2,i3)是的最大值(此时的纵坐标是可以用上面退出来的)。
状态转移：F[k][i1][i2][i3]=max(F[k-1][i1的八种移动情况][i2的八种移动情况][i3的八种移动情况])+x
x是当三人走到(x,y)这个格子的情况时的最优值。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
const int dir[3][8]={
{-1,-1,-1,0,0,0,-1,0},
{-1,-1,0,-1,0,-1,0,0},
{-1,0,-1,-1,-1,0,0,0}
};
int F[60][30][30][30],a[30][30];
int n;
int Max(int x,int y)
{
if (x>y) return x;
else return y;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
memset(F,0,sizeof(F));
int x;
for (int k=2;k<=2*n;k++)
for (int i1=1;i1<=k-1;i1++)
for (int i2=1;i2<=k-1;i2++)
for (int i3=1;i3<=k-1;i3++)
{
x=a[i1][k-i1]+a[i2][k-i2]+a[i3][k-i3];
if (i1==i2 && i1!=i3) x=a[i1][k-i1]+a[i3][k-i3];
if (i1==i3 && i2!=i3) x=a[i1][k-i1]+a[i2][k-i2];
if (i2==i3 && i1!=i3) x=a[i2][k-i2]+a[i1][k-i1];
if (i1==i2 && i2==i3) x=a[i1][k-i1];
for (int i=0;i<=7;i++)
F[k][i1][i2][i3]=Max(F[k][i1][i2][i3],F[k-1][i1+dir[0][i]][i2+dir[1][i]][i3+dir[2][i]]);
F[k][i1][i2][i3]+=x;
}
printf("%d\n",F[2*n][n][n][n]);
return 0;
}