【DP练习】月饼盒（提高版）（vijos1255）

【DP练习】月饼盒（提高版）

          测试链接：https://vijos.org/p/1255

　　【题目背景】:中秋节了，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;
 }