题目: P1006 传纸条

这题虽然跟方格取数很像,但是这题要求两个人的路径严格不相交
减了两条枝,复杂度已经够优秀了

include<bits/stdc++.h>

using namespace std;
#define low(x) x&(-x)
#define ll long long
int m,n;
int mp[55][55];
int f[55][55][55][55];
int main(){
cin >> n >> m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin >> mp[i][j];
}
}

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            for(int i2=1;i2<=n;++i2){
                for(int j2=j+1;j2<=m;++j2){   //保证第二人一定在第一个人的右边
                    if(i2+j2>i+j) break;
                    if(i+j!=i2+j2) continue;
                    int z=max(f[i-1][j][i2-1][j2],f[i-1][j][i2][j2-1]);
                    f[i][j][i2][j2]=max(z,max(f[i][j-1][i2-1][j2],f[i][j-1][i2][j2-1]))+mp[i][j]+mp[i2][j2];
                }
            }
        }
    }
cout << f[n][m-1][n-1][m] << endl;
return 0;

}