本文共 1027 字，大约阅读时间需要 3 分钟。

题目

一个被分为 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

可以送出去的糖果数。

>Sample Input

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

>Sample Output

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

思路

DP，和最大子矩阵（前缀和+求最大子序列o（n^3）做法)。Ctrl+V。

代码

#include<cstdio>int n,m,i,j,k,s,ans,a[301][301]={   0};int main(){   	scanf("%d%d",&n,&m);	for(i=1;i<=n;i++)	  for(j=1;j<=m;j++){   	  	scanf("%d",&a[i][j]);	  	if(a[i][j]==0) a[i][j]=-1000000;//嘻嘻	  	a[i][j]=a[i][j]+a[i][j-1]; //求前缀和	  }	ans=0;	for(i=1;i<=m;i++)	  for(j=i;j<=m;j++){     //枚举俩列	  	s=0;	  	for(k=1;k<=n;k++){     //枚举行	  		if(s+(a[k][j]-a[k][i-1])<(a[k][j]-a[k][i-1])) //因为前面的负数，特殊写法，也是最大子序列求法			s=a[k][j]-a[k][i-1];   			else s=s+a[k][j]-a[k][i-1];			if(s>ans) ans=s;	  	}  	  }	printf("%d",ans);}

转载地址：http://akug.baihongyu.com/