三维dp 测试点二错误 望指正
查看原帖
三维dp 测试点二错误 望指正
335308
DZP102楼主2022/12/3 09:35

我压缩了第一次的列数与第二次的行

#include<bits/stdc++.h>
using namespace std;
int a[51][51],n,m,k=1;
long long dp[61][111][61];
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i1=1;i1<=m;i1++)
        for(k=1;k<=m+n;k++)
            for(int j2=1;j2<=n;j2++){
                if(i1!=k-j2) 
                    dp[i1][k][j2]=max(max(dp[i1-1][k-1][j2],dp[i1][k-1][j2-1]),max(dp[i1-1][k-1][j2-1],dp[i1][k-1][j2]))+a[i1][k-i1]+a[k-j2][j2];
                else
                    dp[i1][k][j2]=-1;
                //cout<<dp[i1][k][j2]<<" "<<i1<<" "<<k<<" "<<j2<<endl;
           }
    cout<<dp[m-1][m+n][n-1]<<endl;
    return 0;
}
2022/12/3 09:35
加载中...