求调,悬关!
查看原帖
求调,悬关!
1385348
Ai_and_Conan楼主2024/11/23 18:15

求调!感觉思路没错 但是连样例都过不去 emmmm

#include<bits/stdc++.h>
using namespace std;
int m,n;
int ma[51][51];
int dp[102][51][51];
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&ma[i][j]);
        }
    }
    dp[0][1][1]=ma[1][1];
    for(int i=1;i<=m+n-2;i++){
        for(int j=1;j<=min(i+1,m);j++){
            for(int k=1;k<=min(i+1,m);k++){
                if(k==j){
                    dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+ma[j][i+3-j]);
                    dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+ma[j+1][i+2-j]);
                    dp[i+1][j+1][k]=max(dp[i][j][k]+ma[j+1][i+2-j]+ma[k][i+3-k],dp[i+1][j+1][k]);
                    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+ma[j][i+3-j]+ma[k+1][i+2-k]);
                }
                else if(j==k+1){
                    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+ma[j][i+3-j]);
                    dp[i+1][j+1][k]=max(dp[i][j][k]+ma[j+1][i+2-j]+ma[k][i+3-k],dp[i+1][j+1][k]);
                    dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+ma[j][i+3-j]+ma[k][i+3-k]);
                    dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+ma[j+1][i+2-j]+ma[k+1][i+2-k]);
                }
                else if(j+1==k){
                    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+ma[j][i+3-j]+ma[k][i+2-k]);
                    dp[i+1][j+1][k]=max(dp[i][j][k]+ma[j+1][i+2-j],dp[i+1][j+1][k]);
                    dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+ma[j][i+3-j]+ma[k][i+3-k]);
                    dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+ma[j+1][i+2-j]+ma[k+1][i+2-k]);
                }
                else if(abs(j-k)>=2){
                    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+ma[j][i+3-j]+ma[k][i+2-k]);
                    dp[i+1][j+1][k]=max(dp[i][j][k]+ma[j+1][i+2-j]+ma[k][i+3-k],dp[i+1][j+1][k]);
                    dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]+ma[j][i+3-j]+ma[k][i+3-k]);
                    dp[i+1][j+1][k+1]=max(dp[i+1][j+1][k+1],dp[i][j][k]+ma[j+1][i+2-j]+ma[k+1][i+2-k]);
                }
            }
        }
    }
    printf("%d",dp[m+n-2][m][n]);
    return 0;
}
2024/11/23 18:15
加载中...