题目背景

王7的生日到了，他的弟弟准备送他巧克力。

题目描述

有一个被分成n*m格的巧克力盒，在(i,j)的位置上有a[i,j]块巧克力。就在送出它的前一天晚上，有老鼠夜袭巧克力盒，某些位置上被洗劫并且穿了洞。所以，你——王7的弟弟王9，必须从这个满目苍夷的盒子中切割出一个矩形巧克力盒，其中不能有被老鼠洗劫过的格子且使这个盒子里的巧克力尽量多。

输入格式

第一行有两个整数 n、m。第 i+1行的第 j 个数表示a[ i , j ]。如果这个数为 0 ，则表示这个位置的格子被洗劫过。

输出格式

输出最大巧克力数。

输入输出样例

输入 #1复制

3 41 2 3 45 0 6 310 3 4 0

输出 #1复制

17//10 3 4这个矩形的巧克力数最大

说明/提示

1≤n,m≤300

0≤a[i,j]≤255

 

这道题。。。

 

吐槽：我从昨天晚上交上去，到今天晚上整整24个小时后它还是“Juding”。。。。。。

 

我觉得我是对的。。。

 

 

#include
      
       #include
       
        #define inf 1<<25#define ll long longusing namespace std;ll n,m;ll map[310][310],s[310],up[310][310];ll ans;int i,j,k;inline int read(){    int s=0,w=1;    char ch=getchar();    while(ch<'0'||ch>'9'){        if(ch=='-'){            w=-1;        }        ch=getchar();    }    while(ch>='0'&&ch<='9'){        s=s*10+ch-'0';        ch=getchar();    }    return s*w;}int main(){    n=read();    m=read();    for(i=1;i<=n;++i){        for(j=1;j<=m;++j){            map[i][j]=read();            if(!map[i][j]){                map[i][j]=-inf;            }            up[i][j]=up[i-1][j]+map[i][j];        }    }    for(i=1;i<=n;++i){        for(j=i;j<=n;++j){            ll mi=0;            for(k=1;k<=m;++k){                s[k]=s[k-1]+up[j][k]-up[i-1][k];            }            for(k=1;k<=m;++k){                ans=max(ans,s[k]-mi);                mi=min(s[k],mi);            }        }    }    printf("%lld\n",ans);    return 0;}