【DP练习】月饼盒（提高版）
【题目背景】:中秋节了，CCC老师决定去送礼。
【问题描述】:一个被分为 n*m 个格子的月饼盒，第 i 行第 j 列位置的格子里面有 a [ i , j ]个月饼。本来CCC老师打算送这盒月饼给某人的，但是就在要送出月饼盒的前一天晚上，一只极其可恶的老鼠夜袭月饼盒，有部分格子被洗劫并且穿了洞。CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒，新的月饼盒不能有洞，并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。
【题目任务】：请帮CCC老师设计一个程序 计算一下新月饼盒最多能够保留多少月饼。
【文件输入】第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i , j ]，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中：1 ≤ n，m ≤ 300 , 0 ≤ a [ i , j ]≤ 255
【文件输出】:输出最大月饼数
【样例输入】
3 4
1 2 3 4
5 0 6 3
10 3 4 0
【样例输出】
17
PS：对于40％的数据，N ，M≤80
对于60％的数据，N ，M≤400
对于100%的数据，N，M≤1000
解题：
题目大意说的很清楚，其中有两个限制条件：
1、切割出来的需要是一个矩形
2、切割出来的矩形里不能有为0的数
首先我们要想的是怎么去切割矩形，这个我们不妨把思路转换一下，让我们来想想一个矩形应该是怎么的出来的？
矩形的构成有两大要素，长和宽，说到这里大家应该有点思路了吧？
没错，有两种方式可以来构建一个矩形
（1）先确定长，然后不断延伸它的宽
（2）先确定宽，然后延伸它的长
这道题我们便可以利用这个思路来解题。
下面我们来分析一下：
假设我们当前遍历到a[0][0],即刚刚开始
1.从a[0][0]出发，向右遍历（注意：我们只需要向右遍历），确认从当前位置出发，所能得到最大的长（遍历到0或者到边界则停止，进入下一步），以此作为矩形的长，我们得到了它的最大长为4，即从a[0][0]-->a[0][3]
2.我们以这个长为中心，上下延伸矩形的宽，可分两步来
（1）往上延伸，遇到0或到达边界则返回，否则继续向上扩展。在例子中，我们往上延伸，第一次就达到了边界，,因此直接返回，往上扩展的宽度为0。
（2）往下延伸，遇到0或到达边界则返回，否则继续向下扩展。在例子中，我们向下延伸，在第一次就遇到了0，因此直接返回，向下延伸的宽度为0。
3.这个时候，就得到了我们想要的矩形了，此时我们在将矩形中数据的和与当前记录的最大值作比较，如果大于最大值则替换最大值。
我们以另一起点再来分析模拟一遍，假设我们当前遍历到了a[1][2]，如下图：
1.我们以a[1][2]为起点，向右遍历（注意：我们只需要向右遍历），确认从当前位置出发，所能得到最大的长（遍历到0或者到边界则停止，进入下一步），以此作为矩形的长，我们得到了它的最大长为2，即从a[1][2]-->a[1][3]
2.我们以这个长为中心，上下延伸矩形的宽，还是分两步来
（1）往上延伸，遇到0或到达边界则返回，否则继续向上扩展。在例子中，我们往上延伸，第一次发现可以满足要求，此时宽+1，继续往上延伸，达到了边界，,因此直接返回，往上扩展的宽度为1。
当前的矩形如图： 
（2）往下延伸，遇到0或到达边界则返回，否则继续向下扩展。在例子中，我们向下延伸，在第一次就遇到了0，因此直接返回，向下延伸的宽度为0。
3.这个时候，就得到了我们想要的矩形了，此时我们在将矩形中数据的和与当前记录的最大值作比较，如果大于最大值则替换最大值。
代码实现：
#include<stdio.h> int n,m,a[305][305]; //往上扩展 int searchup(int miny,int maxy,int x){ // printf("up\n"); int sum = 0; if(x < 0) return 0; for(int i = miny; i <= maxy; i++) { if(a[x][i] == 0) return 0; sum += a[x][i]; } return sum+searchup(miny,maxy,x-1); } //往下扩展 int searchdown(int miny,int maxy,int x){ // printf("down\n"); int sum = 0; if(x > n) return 0; for(int i = miny; i <= maxy; i++) { if(a[x][i] == 0) return 0; sum += a[x][i]; } return sum+searchdown(miny,maxy,x+1); } int main() { int i,j,k; scanf("%d %d",&n,&m); for(i = 0 ; i < n ; i++) for(j = 0 ; j < m ; j++) scanf("%d",&a[i][j]); int max = 0 , sum = 0, miny = -1,maxy = -1; for(i = 0 ; i < n ; i++){ for(k = 0 ; k < m ; k++){ if(a[i][k] == 0) continue; // printf("a[%d][%d]=%d\n",i,k,a[i][k]); for(j = k ; j < m ; j++){ miny = k; sum += a[i][j]; //确定矩形的长 if(a[i][j] == 0 || j == m-1){ maxy = j; if(a[i][j] == 0) maxy--; // printf("前：miny = %d,maxy = %d,sum = %d, i = %d\n",miny,maxy,sum,i); sum += searchup(miny,maxy,i-1); sum += searchdown(miny,maxy,i+1); // printf("后：miny = %d,maxy = %d,sum = %d, i = %d\n",miny,maxy,sum,i); miny = -1; if(sum > max) max = sum; sum = 0; break; } } } } printf("%d\n",max); return 0; }
