NC16615 传纸条

错误思路：一开始想着用贪心，小渊每次都传给好感度最大的同学，并标记这个同学，小轩传递的时候就传递给没传递过的同学中的最大值，如果这样走的话可能会导致有些只比小渊传给的同学的好感度低一点点的同学，在小轩传递的时候并不能传递到。可以看一下这个样例
3 3
0 72 38
80 69 65
68 96 0
小渊走的路径为0->80->69->96->0
小轩走的路径为0->65->38->72>0
可以看到68这个点谁都没有传递，但是如果小渊传递给68，而不是69，那么小轩就可以传递给69，不用传递给38，所以不能一味让小渊传递给最大值，我们还要考虑小轩的情况，如果用上面的思路的话dp[i][j]的意思就是小渊走到(i,j)这个位置的最大好感度。如果我们用dp[i][j][m][n]，它的状态是小渊走到(i,j)位置，小轩走到(m,n)位置的最大好感度
因为小渊从左上角走到右下角，小轩从右下角走到左上角，而且二者走的路线不能相同，我们可以把问题转化为两个人都从左上角走到右下角，但是两个人不能都相同的点

#include<iostream>
using namespace std;
const int maxn=55;
int arr[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];
int m,n;
int main(){    
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                for(int m=1;m<=n;m++){
                    dp[i][j][k][m]=max(dp[i-1][j][k-1][m],max(dp[i-1][j][k][m-1],max(dp[i][j-1][k-1][m],dp[i][j-1][k][m-1])))+arr[i][j]+arr[k][m];
                    if(i==k&&j==m){
                        dp[i][j][k][m]-=arr[i][j];
                    }
                } 
            }
        }
    }
    cout<<dp[m][n][m][n];
    return 0;
} 



////////////////////////优化
#include<iostream>
using namespace std;
const int maxn=55;
int arr[maxn][maxn];
int dp[maxn][maxn][maxn][maxn];
int m,n;
int main(){    
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>arr[i][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=m;k++){
                    int y=i+j-k;
                    if(y<0)continue;
                    dp[i][j][k][y]=max(dp[i-1][j][k-1][y],max(dp[i-1][j][k][y-1],max(dp[i][j-1][k-1][y],dp[i][j-1][k][y-1])))+arr[i][j]+arr[k][y];
                    if(i==k&&j==y){
                        dp[i][j][k][y]-=arr[i][j];
                    }
                    //cout<<"dp["<<i<<"]["<<j<<"]["<<k<<"]["<<m<<"]:"<<dp[i][j][k][m]<<" ";

                //cout<<endl;
            }
            //cout<<endl;
        }
        //cout<<endl;
    }
    cout<<dp[m][n][m][n];
    return 0;
}