30分dp求助,边界可能有问题但我调不出了555
查看原帖
30分dp求助,边界可能有问题但我调不出了555
393674
jixiang楼主2021/10/12 12:11
#include<bits/stdc++.h>
using namespace std;
const int  N=1e3+10;

int f[N][N][4];
int w[N][N];
int n;


int main()
{
    int n,m;
    cin>>n>>m;
    int ans;

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
     {
         f[i][j][0]=-INT_MAX;
         f[i][j][1]=-INT_MAX;
         f[i][j][2]=-INT_MAX;
         cin>>w[i][j];
     }

    f[1][1][0]=w[1][1];
    f[1][1][1]=w[1][1];

    for(int i=2;i<=n;i++)
    {
        f[i][1][0]=w[i][1];
        f[i][1][1]=max(f[i-1][1][0],f[i-1][1][1])+w[i][1];
    }

    for(int i=n-1;i>=1;i--)f[i][1][2]=max(f[i+1][1][2],f[i+1][1][0])+w[i][1];
    for(int j=2;j<=m;j++)
    {
        for(int i=1;i<=n;i++)
        {
            f[i][j][0]=max(f[i][j-1][1],f[i][j-1][0]);
            f[i][j][0]=max(f[i][j][0],f[i][j-1][2]);
            f[i][j][0]+=w[i][j];
            if(i==1)continue;
            f[i][j][1]=max(f[i-1][j][1],f[i-1][j][0])+w[i][j];
        }

        for(int i=n-1;i>=1;i--)f[i][j][2]=max(f[i+1][j][2],f[i+1][j][0])+w[i][j];
    }


    /*for(int i=1;i<=n;i++)
    {for(int j=1;j<=m;j++)cout<<f[i][j][1]<< " "; puts("");}

    for(int i=1;i<=n;i++)
    {for(int j=1;j<=m;j++)cout<<f[i][j][0]<< " "; puts("");}

    for(int i=1;i<=n;i++)
    {for(int j=1;j<=m;j++)cout<<f[i][j][2]<< " "; puts("");}*/


    cout<<max(max(f[n][m][0],f[n][m][1]),f[n][m][2]);


}

2021/10/12 12:11
加载中...