背景

JerryZhou同学经常改编习题给自己做。

这天，他又改编了一题。。。。。

描述

设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。

某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。

在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。

格式

输入格式

第一行:N (4<=N<=20)
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0

输出格式

一行，表示最大的总和。

样例1

样例输入1

4
1 2 3 4
2 1 3 4
1 2 3 4
1 3 2 4

样例输出1

39

限制

各个测试点1s

提示

多进程DP

 

我的做法

就是多进程DP..dp[s][i][j][k]表示都走了s部，其中第几个向右走了几步，那么我们同时就可以得出向下走了几步，因为每次不是向右就是向下...

代码：

[code lang="cpp"]
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int g[30][30];
int dp[60][30][30][30];
int solve(){
dp[1][1][1][1] = g[1][1];
for (int s = 2; s <= 2 * n; s++)
for (int i = 1; i <= min(n, s); i++)
for (int j = 1; j <= min(n, s); j++)
for (int k = 1; k <= (n, s); k++){
// cout << "fun!" << endl;
int tmp = -INF;
tmp = max(tmp, dp[s - 1][i][j][k]);
tmp = max(tmp, dp[s - 1][i - 1][j][k]);
tmp = max(tmp, dp[s - 1][i - 1][j - 1][k]);
tmp = max(tmp, dp[s - 1][i - 1][j][k - 1]);
tmp = max(tmp, dp[s - 1][i - 1][j - 1][k - 1]);
tmp = max(tmp, dp[s - 1][i][j - 1][k]);
tmp = max(tmp, dp[s - 1][i][j - 1][k - 1]);
tmp = max(tmp, dp[s - 1][i][j][k - 1]);
if (i == j && j == k) tmp += g[s - k + 1][k];
else if (i == j) tmp += g[s - i + 1][i] + g[s - k + 1][k];
else if (i == k) tmp += g[s - j + 1][j] + g[s - k + 1][k];
else if (j == k) tmp += g[s - i + 1][i] + g[s - j + 1][j];
else tmp += g[s - i + 1][i] + g[s - j + 1][j] + g[s - k + 1][k];
dp[s][i][j][k] = tmp;
// cout << tmp << endl;
}

return dp[2 * n - 1][n][n][n];
}

int main(){
cin >> n;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) cin >> g[i][j];
cout << solve() << endl;
}
[/code]