WangYXHaHa

实在鸡冻，没想到竟然一次性过！

这道题是让算取两次数的最大的和，因为第一次的取法会对第二次的取法有所干扰，所以我们可以让这个人把两次取数合并为一次，也就是说让两个人同时取数，我们就可以把原取数规则改一下：

1. 只能向右或向下走，从A走到B

2. 当两个人走到同一个点上时，自然把这个数让给第一个人

这题不是背包，动态转移方程需要自己DIY。

首先设 $\text{dp}\left\lbrack i \right\rbrack\left\lbrack j \right\rbrack\left\lbrack k \right\rbrack\left\lbrack l \right\rbrack$ 表示当第一个人走到第 $i$ 行第 $j$ 列，第二个人走到第 $k$ 行第 $l$ 列时的最大的和，$W\left\lbrack i \right\rbrack\left\lbrack j \right\rbrack$ 表示第 $i$ 行第 $j$ 列上的数的值。

不难看出，此时需要分类讨论：

1. 当两个人走到同一个点上时

2. 当两个人没走到同一个点上时

于是乎我们的动态转移方程还要分两个:

1. 当两个人走到同一个点上时:

$dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack\lbrack l\rbrack = max(dp\lbrack i - 1\rbrack\lbrack j\rbrack\lbrack k - 1\rbrack\lbrack l\rbrack,dp\lbrack i - 1\rbrack\lbrack j\rbrack\lbrack k\rbrack\lbrack l - 1\rbrack,dp\lbrack i\rbrack\lbrack j - 1\rbrack\lbrack k - 1\rbrack\lbrack l\rbrack,dp\lbrack i\rbrack\lbrack j - 1\rbrack\lbrack k\rbrack\lbrack l - 1\rbrack)) + w\lbrack i\rbrack\lbrack j\rbrack;$

2. 当两个人没走到同一个点上时:

$dp\lbrack i\rbrack\lbrack j\rbrack\lbrack k\rbrack\lbrack l\rbrack = max(dp\lbrack i - 1\rbrack\lbrack j\rbrack\lbrack k - 1\rbrack\lbrack l\rbrack,dp\lbrack i - 1\rbrack\lbrack j\rbrack\lbrack k\rbrack\lbrack l - 1\rbrack,dp\lbrack i\rbrack\lbrack j - 1\rbrack\lbrack k - 1\rbrack\lbrack l\rbrack,dp\lbrack i\rbrack\lbrack j - 1\rbrack\lbrack k\rbrack\lbrack l - 1\rbrack)) + w\lbrack i\rbrack\lbrack j\rbrack + w\lbrack k\rbrack\lbrack l\rbrack;$

实际上也不难看出两种情况的区别就在于有没有加上第二个人取到的值。

于是乎代码如下：

#include <iostream>
using namespace std;

int dp[9+5][9+5][9+5][9+5],w[9+5][9+5];
bool u[9+5][9+5];

int main(){
    int n;
    cin >> n;
    while (1){
        int high,wide,m;
        cin >> high >> wide >> m;
        if (high==0 && wide==0 && m==0){
            break;
        }
        w[high][wide]=m;
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            for (int k=1;k<=n;k++){
                for (int l=1;l<=n;l++){
                    if (i==k && j==l){
                        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]))+w[i][j];
                    }
                    else{
                        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]))+w[i][j]+w[k][l];
                    }
                }
            }
        }
    }
    cout << dp[n][n][n][n] << endl;
    return 0;
}

完成！

不过还是有小问题的：

似乎这道题能将数组优化至三维？（看别的题解是这样的，不过没看懂）