题解

1 条题解

  • 0
    @ 2017-10-03 13:58:34

    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>
    #include <assert.h>
    using namespace std;
    int n,m,a[305][305],MIN[305],b[305],dp[305][2],i,j,s[305][305],ans,P,k;
    int main()
    {
    while (cin>>n)
    {
    ans=-1000000000;
    scanf("%d%d",&m,&P); assert(1<=n && n<=300 && 1<=m && m<=300 && -1000<=P && P<=1000);
    for (i=1; i<=n; i++)
    for (j=1; j<=m; j++) {scanf("%d",&a[i][j]); assert(-1000<=a[i][j] && a[i][j]<=1000); }
    for (i=1; i<=n; i++)
    for (j=1; j<=m; j++)
    s[i][j]=s[i-1][j]+a[i][j];
    for (i=1; i<=n; i++)
    {
    for (j=1; j<=m; j++) MIN[j]=a[i][j];
    for (j=i; j<=n; j++)
    {
    for (k=1; k<=m; k++) MIN[k]=min(MIN[k],a[j][k]);
    for (k=1; k<=m; k++) b[k]=s[j][k]-s[i-1][k]; dp[0][1]=-1000000000;
    for (k=1; k<=m; k++) dp[k][0]=max(dp[k-1][0]+b[k],b[k]),dp[k][1]=max(max(dp[k-1][1]+b[k],dp[k-1][0]+b[k]-MIN[k]+P),b[k]-MIN[k]+P);
    for (k=1; k<m; k++) ans=max(ans,max(dp[k][0],dp[k][1]));
    if (i==1 && j==n)
    {
    ans=max(ans,dp[m][1]); int sum=0;
    for (k=m; k>1; k--) {sum+=b[k]; ans=max(ans,sum);}
    } else
    ans=max(ans,max(dp[m][1],dp[m][0]));
    }
    }
    cout<<ans<<endl;
    }
    return 0;
    }

  • 1

信息

难度
9
分类
(无)
标签
(无)
递交数
3
已通过
1
通过率
33%
上传者