旅行

Description

ACM队员们到Z镇游玩，Z镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成MN个区域。Z镇的名胜位于这些区域内，从上往下第i行，从左往右数第j列的区域记为D（i,j）。ACM队员们预先对这MN个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一个范围内活动。我们可以用(m1,n1)与(m2,n2)(m1<=m2，n1<=n2)表示这样一个范围：它是这些区域的集合： ，ACM队员希望他们活动区域的分值总和最大。
当然，有的队员可能一个也不去（例如，所有区域的分值都是负数。当然，如果某范围内的分值和为0的话，他们也不会去玩）。也有可能他们游览整个Z镇。你的任务是编写一个程序，求出他们的活动范围(m1,n1),(m2,n2)。

Input

输入有m+1行，第一行有两个整数m,n（m,n定义如上）。其中( )，接下来的m行，每行n个整数，第i行第j个数表示分数V(i,j)。（-128<=v(i,j)<=127）每两个整数之间有一个空格。

Output

输入只一行，分两种情况：
1． 队员在范围内(m1,n2)(m2,n2)内活动，输出该范围内的分值。
2． 队员们任何地方都不去，只需输出NO。
注意：不要输出多余的空行，行首行尾不要有多余的空格。

Sample Input

样例1

4 5
1 -2 3 -4 5
6 7 8 9 10
-11 12 13 14 -15
16 17 18 19 20

样例2

2 3
-1 -2 -1 
-4 -3 -6

Sample Output

样例1

146

样例2

NO

解题思路

这道题的方法其实是把b[i][j]等于它的上一行加上它的前一个再减去它的左上角的数再加上它本身，然后找出最大值，输出就行了。
状态转移方程：
$b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];$
$maxn=max(b[i][j],maxn);$

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int a[1010][1010],b[1010][1010],maxn=0;
int main()
{
   
	int n,m,ok=0;
	cin>>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) ok=1;
	 }
	if(ok==0){
   
		cout<<"NO";//判断要不要输出NO
		return 0;
	}
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=m;j++)
	{
   
		b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+a[i][j];
		maxn=max(b[i][j],maxn);//状态转移方程
	}
	cout<<maxn;
	return 0;
}