LuoguP1004 方格取数 (4维dp)

题目：

• n*n的表格中，先后选两条路径,第一条路径走完后会清空路径上的值，问两次路径上的值和得最大值。
• (dp[i][j][k][l] = max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]) + val[i][j] + val[k][l])
  注意:如果(i,j)和(k,l)是同一个点的话要减去重复加的部分val[i][j].

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
const int N = 50;
const int mod = 998244353;
const double Pi = acos(- 1.0);
const ll INF = 1e12;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//

int val[N][N];
int n;                                                                                                                                                                    
int dp[N][N][N][N];
int a, b, c;



int solve(){
    rep(i,1,n){
        rep(j,1,n)
            rep(k,1,n)
                rep(l,1,n){
                   dp[i][j][k][l] = max(max(dp[i - 1][j][k - 1][l],dp[i - 1][j][k][l - 1]),max(dp[i][j - 1][k - 1][l],dp[i][j - 1][k][l - 1])) + val[i][j] + val[k][l];
                    if(i == k && j == l) dp[i][j][k][l] -= val[i][j];                  
                }
    }
    return dp[n][n][n][n];
}

int main()
{
    scanf("%d",&n);
    while(scanf("%d%d%d",&a,&b,&c)){
        if(!a&&!b&&!c) break;
        val[a][b] = c;
    }
    int res = solve();
    printf("%d
",res);
    return 0;
}