题解

1 条题解

  • 0
    @ 2018-11-16 19:33:24
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=205;
    const int INF=100000000;
    int N,M,ans;
    int minval,maxval,tmp1,tmp2;
    int a[MAXN][MAXN],tmp[MAXN][MAXN];
    int p[MAXN][MAXN],q[MAXN][MAXN],dp[MAXN];
    void Transpose(){
        for (int i=1;i<=M;i++)
            for (int j=1;j<=N;j++)
                tmp[i][j]=a[j][M-i+1];
        swap(N,M);
        memset(a,0,sizeof(a));
        for (int i=1;i<=N;i++)
            for (int j=1;j<=M;j++)
                a[i][j]=tmp[i][j];
    }
    void Solve(){
        memset(p,0,sizeof(p));
        memset(q,0,sizeof(q));
        for (int i=1;i<=N;i++){
            memset(dp,0,sizeof(dp));
            maxval=-INF,minval=INF;
            for (int j=i;j<=N;j++){
                tmp1=tmp2=0;
                for (int k=1;k<=M;k++){
                    dp[k]+=a[j][k];
                    tmp1+=dp[k],tmp1=max(tmp1,0);
                    maxval=max(maxval,tmp1);
                    tmp2+=dp[k],tmp2=min(tmp2,0);
                    minval=min(minval,tmp2);
                }
                p[i][j]=maxval,q[i][j]=minval;
            }
        }
        for (int i=1;i<=N-1;i++)
            for (int j=i;j<=N-1;j++){
                ans=max(ans,p[i][j]*p[j+1][N]);
                ans=max(ans,q[i][j]*q[j+1][N]);
            }
    }
    int main(){
        scanf("%d%d",&N,&M);
        for (int i=1;i<=N;i++)
            for (int j=1;j<=M;j++)
                scanf("%d",&a[i][j]);
        if (N*M==2){
            if (N==1) printf("%d",a[1][1]*a[1][2]);
            if (M==1) printf("%d",a[1][1]*a[2][1]);
            return 0;
        }
        Solve();
        Transpose();
        Solve();
        printf("%d",ans);
        return 0;
    }
    
  • 1

信息

难度
10
分类
(无)
标签
(无)
递交数
7
已通过
0
通过率
0%
上传者