描述
设有N*N的方格图，我们将其中的某些方格填入正整数，而其他的方格中放入0。某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
格式
输入格式
第一行:N (4<=N<=20)
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0输出格式
一行，表示最大的总和。
样例1
样例输入1
41 2 3 42 1 3 41 2 3 41 3 2 4
样例输出1
39
限制
各个测试点1s
提示
多进程DP
f[step][x1][x2][x3]表示当走到第step步时，三个点分别取x1,x2,x3时的最优解。
由于只能向下或向右移动，所以当移动步数一定时，所能移动到的格子是一个 / 的对角线，所以枚举三次移动到的横坐标，可以O(1)第算出纵坐标，注意每个方格只能取一次。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 const int maxn=25; 9 int f[maxn*2][maxn][maxn][maxn];10 int map[maxn][maxn];11 int N;12 int main(){13 14 scanf("%d",&N);15 for(int i=1;i<=N;i++){16 for(int j=1;j<=N;j++){17 scanf("%d",&map[i][j]);18 }19 }20 f[1][1][1][1]=map[1][1];21 for(int step=2;step<=2*N-1;step++){ //枚举步数,假定走到 (1,1) 用了一步 22 for(int x1=max(1,step-N+1);x1<=min(N,step);x1++){ //x1,x2,x3 是用 step步走到横坐标为 x1,x2,x3的方格,23 for(int x2=max(1,step-N+1);x2<=min(N,step);x2++){ //用min(),max()都是保证方格不越界的方式 24 for(int x3=max(1,step-N+1);x3<=min(N,step);x3++){25 int delta=map[x1][step-x1+1]+map[x2][step-x2+1]+map[x3][step-x3+1];26 if(x1==x2) delta-=map[x1][step-x1+1];27 if(x1==x3) delta-=map[x1][step-x1+1];28 if(x2==x3) delta-=map[x2][step-x2+1];29 if(x1==x2&&x1==x3) delta+=map[x1][step-x1+1];//多减去了一次 30 31 f[step][x1][x2][x3]=max(f[step-1][x1][x2][x3],max(f[step-1][x1-1][x2][x3],32 max(f[step-1][x1][x2-1][x3],max(f[step-1][x1][x2][x3-1],33 max(f[step-1][x1-1][x2-1][x3],max(f[step-1][x1-1][x2][x3-1],34 max(f[step-1][x1][x2-1][x3-1],f[step-1][x1-1][x2-1][x3-1])))))))+delta;35 36 37 }38 }39 }40 }41 cout<