传纸条 and 方格取数 （线性DP，解题关键）

• 两条路径同时进行，设走到的坐标分别为 ( i , j ) , ( x , y ) (i,j),(x,y) (i,j),(x,y)

  容易发现，同一时刻， i + j = x + y i+j=x+y i+j=x+y （解题关键点） , 故还可以降一维

• 并且题目还有一条件，同一点只能经过一条路径

  这好办，即当 i = x i=x i=x 时，两点才会在同一点，将这种情况去掉即可

• 设 f [ i ] [ j ] [ x ] f[i][j][x] f[i][j][x] 表示一点传递到 ( i , j ) (i,j) (i,j)，另一点传递到 ( x , y ) (x,y) (x,y) 的最大值

• 然后 4 4 4 种状态转移见代码

#include 
using namespace std;

const int N=52;
int f[N][N][N],d[N][N];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) cin>>d[i][j];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int x=1;x<=n;x++)
            {
                int y=i+j-x; // 同时传递
                if(y<=0 || i==x || j==y) continue; 
                f[i][j][x]=max(f[i-1][j][x],max(f[i-1][j][x-1],max(f[i][j-1][x],f[i][j-1][x-1])))+d[i][j]+d[x][y];
            }
    cout< 
方格取数 
分析： 
两道题没什么区别，处理条件调整一下即可
 
#include 
using namespace std;

const int N=52;
int f[N][N][N],d[N][N];
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    int x,y,w;
    while(cin>>x>>y>>w && x) d[x][y]=w;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int x=1;x<=n;x++)
            {
                int y=i+j-x;
                if(y<=0) break;
                f[i][j][x]=max(f[i-1][j][x],max(f[i-1][j][x-1],max(f[i][j-1][x],f[i][j-1][x-1])))+d[i][j]+d[x][y];
                if(i==x) f[i][j][x]-=d[i][j]; // 一个点只能加一次
            }
    cout<