$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

推导：

$1\ 号与\ 2\ 号走的步数相同：k=i_1+j_1=i_2+j_2$
$公式变换：j_1=k-i_1,j_2=k-i_2$
$则\ f[k][i_1][j_1][i_2][j_2]=f[k][i_1][k-i_1][i_2][k-i_2]\Rightarrow f[k][i_1][i_2]$

思路：

• $1. 状态表示$
  $集合：从\ (1,1),(1,1)\ 走到\ (i_1,j_1),(i_2,j_2)\ 的所有路线$
  $属性：\max$

• $2. 状态转移$
  $1\ 号从\ (i_1,j_1)\ 上方走来，2\ 号从\ (i_2,j_2)\ 上方走来：f[k][i_1][i_2]=f[k-1][i_1-1][i_2-1]+w[i_1][j_1]$
  $1\ 号从\ (i_1,j_1)\ 上方走来，2\ 号从\ (i_2,j_2)\ 左方走来：f[k][i_1][i_2]=f[k-1][i_1-1][i_2]+w[i_1][j_1]$
  $1\ 号从\ (i_1,j_1)\ 左方走来，2\ 号从\ (i_2,j_2)\ 上方走来：f[k][i_1][i_2]=f[k-1][i_1][i_2-1]+w[i_1][j_1]$
  $1\ 号从\ (i_1,j_1)\ 左方走来，2\ 号从\ (i_2,j_2)\ 左方走来：f[k][i_1][i_2]=f[k-1][i_1][i_2]+w[i_1][j_1]$
  $若\ 1\ 号和\ 2\ 号不是同一个点，则\ f[k][i_1][i_2]\ +=w[i_2][j_2]$

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
int w[N][N];
int f[N*2][N][N]; //从 (1,1),(1,1) 走到 (i1,j1),(i2,j2) 的最大数字和

int main()
{
    cin>>n;

    int a,b,c;
    while(cin>>a>>b>>c,a||b||c) w[a][b]=c;

    for(int k=1;k<=n*2;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) //判断该点是否合法
                {
                    // 1 号和 2 号都往下走
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2-1]+w[i1][j1]);

                    // 1 号往下走，2 号往右走
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1-1][i2]+w[i1][j1]);

                    // 1 号往右走，2 号往下走
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2-1]+w[i1][j1]);

                    // 1 号和 2 号都往右走
                    f[k][i1][i2]=max(f[k][i1][i2],f[k-1][i1][i2]+w[i1][j1]);

                    //不是同一个点
                    if(i1!=i2) f[k][i1][i2]+=w[i2][j2];
                }
            }

    cout<<f[n*2][n][n]<<endl; //从 (1,1),(1,1) 走到 (n,n),(n,n) 的最大数字和

    return 0;
}