题解

1 条题解

  • 2
    @ 2020-08-04 20:58:50
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #include<cstdlib>
    #define gc getchar()
    #define ll long long
    #define ull unsigned long long
    #define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
    #define I inline 
    using namespace std;
    const int N=805,M=N+5;const ull G=31;
    template<class o>I void qr(o &x)
    {
        char c=gc;int f=1;x=0;
        while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
        while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
        x*=f;
    }
    template<class o>I void qw(o x)
    {
        if(x<0)x=-x,putchar('-');
        if(x/10)qw(x/10);
        putchar(x%10+48);
    }
    I void cmx(ll &a,ll b){if(a<b)a=b;}
    ll col[N][N],row[N][N],f[N][N][2],L[N],R[N],s[N],u[N][2],d[N][2],ans;int val[N][N],n,m,arr[N][N];
    void calc()
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                col[i][j]=col[i-1][j]+val[i][j],
                row[i][j]=row[i][j-1]+val[i][j];
        memset(f,0xcf,sizeof(f));
        for(int i=1;i<=n;i++)f[i][1][1]=col[i][1],f[i][1][0]=val[1][1];
        for(int i=1;i<=m;i++)f[1][i][1]=val[1][1],f[1][i][0]=row[1][i];
        for(int i=2;i<=n;i++)
            for(int j=2;j<=m;j++)
            {
                ll w=col[i][j]+row[i][j]-val[i][j];
                cmx(f[i][j][0],f[i-1][j][0]);
                cmx(f[i][j][0],f[i-1][j-1][1]+w);
                cmx(f[i][j][0],f[i][j-1][0]+val[1][j]);
                cmx(f[i][j][1],f[i][j-1][1]);
                cmx(f[i][j][1],f[i-1][j-1][0]+w);
                cmx(f[i][j][1],f[i-1][j][1]+val[i][1]);
            }
        memset(L,0xcf,sizeof(L));memset(R,0xcf,sizeof(R));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cmx(L[i],f[i][j][1]);
        for(int i=1;i<=m;i++)s[i]=row[1][m]-row[1][i];
        R[1]=row[1][m];
        for(int i=2;i<=n;i++)
            for(int j=1;j<m;j++)
            {
                s[j]=max(s[j]+val[i][m],col[i][j+1]+row[i][m]-row[i][j+1]);
                cmx(R[i],f[i][j][0]+s[j]);
            }
    }
    void solve()
    {
        memcpy(val,arr,sizeof(val));calc();
        for(int i=1;i<=n;i++)u[i][0]=L[i],u[i][1]=R[i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                val[i][j]=arr[n-i+1][m-j+1];
        calc();for(int i=1;i<=n;i++)d[i][0]=R[n-i+1],d[i][1]=L[n-i+1];
        memcpy(val,arr,sizeof(val));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                col[i][j]=col[i-1][j]+val[i][j],
                row[i][j]=row[i][j-1]+val[i][j];
        ll l=0,r=row[1][m-1];
        for(int i=2;i<=n;i++)
        {
            cmx(u[i][0],l+col[i][1]);
            cmx(u[i][1],r+col[i][m]);
            cmx(u[i][0],r+col[i][m]+row[i][m]-val[i][m]);
            cmx(u[i][1],l+col[i][1]+row[i][m]-val[i][1]);
            cmx(l,u[i][0]-col[i][1]);
            cmx(r,u[i][1]-col[i][m]);
        }
        l=row[n][m],r=val[n][m];
        cmx(ans,d[1][0]);
        cmx(ans,u[n][1]);
        for(int i=n-1;i>1;--i)
        {
            l=max(l+val[i][1],d[i][0]);
            r=max(r+val[i][m],d[i][1]);
            cmx(ans,l+u[i-1][0]);
            cmx(ans,r+u[i-1][1]);
        }
    }
    int main()
    {
        qr(n),qr(m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                qr(arr[i][j]);
        solve();
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=m;j++)
                swap(arr[i][j],arr[j][i]);
        swap(n,m);
        solve();
        qw(ans);puts("");
        return 0;
    }
    
  • 1

信息

ID
1996
难度
2
分类
(无)
标签
递交数
28
已通过
22
通过率
79%
被复制
2
上传者