多线程四维DP - 洛谷P1004方格取数

题意：洛谷p1004

给定一个$N×N$N×N的矩阵，初始你在点$(1,1)$(1,1)处，现找两条路径(只能往下或往右走，点可重复走，但走过的点权值变为$0$0)走到点$(N,N)$(N,N)处，使得你得到的权值之和最大。

分析：

不会$DP$DP的我看到这题第一想法就是跑两遍$DP$DP然后求和，然而$WA$WA。事实是跑两遍$DP$DP本质上和贪心是一样的，所以$WA$WA。然后我就学到了传说中的四维$DP$DP(然而可以降到三维我不会 )。
首先，$dp[i][j][k][u]$dp[i][j][k][u]表示从起点$(1,1)$(1,1)走到点$(i,j)$(i,j)和点$(k,u)$(k,u)最大权值之和。
因为只能往下和往右走，所以有四种状态转移。
$1.$1.第一条路往右，第二条路往下
$2.$2.第一条路往右，第二条路往右
$3.$3.第一条路往下，第二条路往下
$4.$4.第一条路往下，第二条路往右
要从这四个状态转移出最大的，所以有状态转移方程
$dp[i][j][k][u] =max(max(dp[i][j-1][k-1][u],dp[i][j-1][k][u-1]),max(dp[i-1][j][k-1][u], dp[i-1][j][k][u-1]))+pic[i][j]+pic[k][u]$dp[i][j][k][u]=max(max(dp[i][j−1][k−1][u],dp[i][j−1][k][u−1]),max(dp[i−1][j][k−1][u],dp[i−1][j][k][u−1]))+pic[i][j]+pic[k][u]
因为是走到点$(i,j)$(i,j)和点$(k,u)$(k,u)所以还要加上他们本身的权值。
需要注意的一点，当$(i,j)$(i,j)和$(k,u)$(k,u)相等时，只用加一次$pic[i][j]$pic[i][j]。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 10 + 5;

int n, x, y, z, pic[maxn][maxn], dp[maxn][maxn][maxn][maxn];

int main(){
	cin >> n;
	while(cin >> x >> y >> z){
		if(x == 0 && y == 0 && z == 0) break;
		pic[x][y] = z;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++){
				for(int u = 1; u <= n; u++){
					dp[i][j][k][u] = max(max(dp[i - 1][j][k - 1][u], dp[i - 1][j ][k][u - 1]), max(dp[i][j - 1][k - 1][u], dp[i][j - 1][k][u - 1])) + pic[i][j] + pic[k][u];
					if(i == k && j == u) dp[i][j][k][u] -= pic[i][j];
				}
			}
		}
	}
	cout << dp[n][n][n][n] << '\n';
    return 0;
}

加油学$dp$dp