糖果盒

Description

一个被分为 n*m　个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。
请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果。

Input

从文件CANDY.IN读入数据。第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i ][ j ]，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中：
1 ≤ n，m ≤ 300
0 ≤ a [ i ][ j ]≤ 255

Output

输出最大糖果数到 CANDY.OUT。

Sample Input

3 4
1  2  3  4
5  0  6  3
10 3  4  0

Sample Output

17

注：
10 3 4
这个矩形的糖果数最大

Hint

数据规模：
40%的数据1 ≤ n，m ≤ 300

解题思路

这道题其实就是在旅行这道题上做了些许改变，只用把赋初值赋为一个比零小很多的数。
动态转移方程：$b[k]=c[j][k]-c[i-1][k];$

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int a[1010][1010],b[1010],c[1010][1010],n,m;
int main()
{
   
	scanf("%d",&n,&m);
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	  {
   
		    cin>>a[i][j];
			if(a[i][j]==0) a[i][j]=-31950000;//赋初值
			c[i][j]=c[i-1][j]+a[i][j];
	  }
	int t=0,s=0;
	for(int i=1;i<=n;i++)
	 for(int j=i;j<=n;j++)
	  {
   
		   s=0;
		   for(int k=1;k<=m;k++) 
		   {
   
		        b[k]=c[j][k]-c[i-1][k];//动态转移方程
		   }
		   for(int k=1;k<=m;k++)
		   {
   
				s+=b[k];
				if(s>t) t=s;//找最大值
				if(s<0) s=0;
	 	   }
	  }
	if(t<=0) printf("%s","NO");
	else printf("%d",t);
    return 0;
}