解题思路

前置题目：摘花生

做这个题之前要先将抽象思维打开，这个题看似就像两次摘花生，但是两次不能摘相同的，而且这个第一次摘完之后的路径不太好记录（或许是不能记录），那么我们就把二维的抽象成四维；就表示这两次摘花生要同时进行，那么只需要判断他们两个什么时候会重合，如果重合只记录一次；如果不重合记录两次；

AC （四维）

#include <iostream>

using namespace std;

const int N = 15;
int w[N][N];
int f[N][N][N][N];
int n;

int main() {
    scanf("%d",&n);
    int l,r,d;
    while(scanf("%d%d%d",&l,&r,&d),l || r || d) w[l][r] = d;
    // k = i + j;

    for(int i1 = 1;i1 <= n;i1++)
        for(int j1 = 1;j1 <= n;j1++)
            for(int i2 = 1;i2 <= n;i2++)
                for(int j2 = 1;j2 <= n;j2++) 
                    {
                        // 判断是否重合
                        int t = w[i1][j1];
                        // 不重合，两个都加
                        if(i1 != i2) t += w[i2][j2];
                        // 通过引用的方式简化写法
                        int &x = f[i1][j1][i2][j2];
                        // 状态转移
                        // 第一种情况：向下到达的 第二条：向下到达的
                        x = max(x,f[i1-1][j1][i2-1][j2]+t);
                        // 第二种情况：向下到达的 第二条：向右到达的
                        x = max(x,f[i1-1][j1][i2][j2-1]+t);
                        // 第三种情况：向右到达的 第二条：向下到达的
                        x = max(x,f[i1][j1-1][i2-1][j2]+t);
                        // 第四种情况：向右到达的 第二条：向右到达的
                        x = max(x,f[i1][j1-1][i2][j2-1]+t);
                    }

    printf("%d",f[n][n][n][n]);
    return 0;
}

AC （优化三维）

这里优化成三维的原因是，他们两个移动之后的横纵坐标相加一定是相同的，因为每次只能向下或者向右，总和每次都是+1；

#include <iostream>

using namespace std;

const int N = 15;
int w[N][N];
int f[N*2][N][N];
int n;

int main() {
    scanf("%d",&n);
    int l,r,d;
    while(scanf("%d%d%d",&l,&r,&d),l || r || d) w[l][r] = d;
    // k = i + j;
    for(int k = 2;k <= n+n;k++)
        for(int i1 = 1;i1 <= n;i1++)
            for(int i2 = 1;i2 <= n;i2++) {
                // 获取纵坐标
                int j1 = k - i1,j2 = k - i2;

                // 判断范围
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n) {
                    // 判断是否重合
                    int t = w[i1][j1];
                    // 不重合，两个都加
                    if(i1 != i2) t += w[i2][j2];
                    // 通过引用的方式简化写法
                    int &x = f[k][i1][i2];
                    // 状态转移
                    // 第一种情况：向下到达的 第二条：向下到达的
                    x = max(x,f[k-1][i1-1][i2-1]+t);
                    // 第二种情况：向下到达的 第二条：向右到达的
                    x = max(x,f[k-1][i1-1][i2]+t);
                    // 第三种情况：向下到达的 第二条：向右到达的
                    x = max(x,f[k-1][i1][i2-1]+t);
                    // 第四种情况：向右到达的 第二条：向右到达的
                    x = max(x,f[k-1][i1][i2]+t);
                }
            }

    printf("%d",f[n+n][n][n]);
    return 0;
}