luogu1565 牛宫

- 日理万妓 2021-10-29 13:24 204阅读 0赞

## 题目 ##

Description  
\_AP神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块N\*M的矩形空地。空地中每个格子都有自己的海拔高度。AP想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，AP希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问AP的宫殿最后会有多大？  
Input Format  
第一行为N和M。之后N行，每行M个数，描述的空地的海拔。  
Output Format  
输出一行,表示宫殿最大面积。  
\_  
Sample Input  
3 2  
4 0  
\-10 8  
\-2 -2

Sample Output  
4

Data Limit  
对于30%的数据，N,M≤50;  
对于100%的数据，N,M≤200；

## 分析 ##

思路是一步一步走向正解的

乍一看还以为是最大子矩阵的题，然而发现这个这个限制与一般最大子矩阵的题不同，是需要平均数大于0，这个限制并不是规则的。动规显然不可行。

看数据范围，正解应该是一个n3或n3logn的算法

因为所求为平均数大于0的最大子矩阵，这个限制于矩阵的和有关，为了简便运算，可以用前缀和，方便求出区间的和，直接判断和是否大于零即可。

**前置知识：二维前缀和（大佬们可以无视这个）**

sum\[i\]\[j\]表示（1,1）到（i，j）这个矩阵的和；

则（a，b）（左上角）到（c，d）（右下角）的和怎么表示？

![1590702-20190815151250822-670686825.png][]

**50分做法**

暴力的贪心是O（n4）的复杂度。

两种思路，一枚举点，二枚举边；

**枚举点：**

枚举矩阵的右下角与左上角顶点。

加了一个小优化（然而并没有什么用），不过最坏还是会退化到O（n4）；

这个优化并不能做到面积严格单调，但是可以大致单调；枚举坐标改为枚举坐标和，则枚举的顺序变成了斜线：

![1590702-20190815115219459-682638813.png][]

细节请看代码注释

注意要开longlong，二维前缀和注意细节

1     long long ans = 0;
     2     for(int i = 1;i <= n; ++ i)
     3     for(int j = 1;j <= m; ++ j)//前两维枚举右下顶点 
     4         for(int s = 2;s <= i + j; ++ s){
        //这一维是左上顶点的坐标和 
     5         //一个小优化，i - k + 1 + j - l + 1是矩形的长宽和
     6         //如果当前答案已经大于了剩下的最大矩形，则不必再枚举 
     7             if(ans > ((double)i + j - s + 2) * (i + j - s + 2) / (double)4) break;
     8             for(int l = max(s - i,1);l <= min(s - 1,j); ++ l){
        //左上顶点的纵坐标 
     9                 int k = s - l;//横坐标 
    10                 if(k < 1 || k > i) continue; 
    11                 long long cur = sum[i][j] - sum[k - 1][j] - sum[i][l - 1] + sum[k - 1][l - 1];
    12                 //二维前缀和，注意细节 
    13                 if(cur > 0) ans = max(ans,((long long)i-k+1) * (j-l+1));//更新答案 
    14             }
    15         }
    16     
    17     put(ans);

**枚举边：**

其实与枚举点差不多，不过要转换思维，就是枚举长宽，相对于这道题来说，枚举边的方法更容易优化。

直接枚举长度显然不太现实，为了便于确定矩阵，我们枚举长度 +下界

1     long long ans = 0;
     2     for(int i = n;i >= 1; -- i){
        //枚举长 
     3         if(ans > i * m) break;//剪枝 
     4         for(int k = m;k >= 1; -- k){
        //枚举宽 
     5             if(ans > i * k) break;//剪枝 
     6             long long s = i * k;
     7             for(int j = i;j <= n;++ j){
        //枚举长的下界 
     8                 int j1 = j - i + 1;
     9                 for(int l = k;l <= m; ++ l){
        //枚举宽的下界 
    10                     int l1 = l - k + 1;
    11                     long long cur = sum[j][l] - sum[j1 - 1][l] - sum[j][l1 - 1] + sum[j1 - 1][l1 - 1];
    12                     if(cur > 0) ans = max(ans,s);
    13                 }
    14             }
    15         } 
    16     }
    17     put(ans);

其实还有一种优化就是像上面枚举点的那样枚举长宽之和，但是没什么太大的用处，优化不明显，且难以进一步优化；

**100分做法**

我们仔细观察枚举边的那一分代码，其实也是做了很多无用功的。

用倒序就是为了避免一些不必要的枚举。

如果我们能在O（1）或者O（log）的时间内求出矩形的长所对应的最大宽，这题就可以切了。

你想到了什么？二分（单调栈）

二分宽度，判断这个宽度（及以上）是否可行。

有了这个想法是不错的，但该如何实现呢？

先看主模块：

1     int ans = 0;
     2     
     3     for(int i = n;i >= 1; -- i){
        //枚举长 
     4         if(ans > i * m) break;//剪枝 
     5         for(int j = i;j <= n; ++ j){
        //枚举长的下界 
     6             for(int k = 1;k <= m; ++ k){
        //预处理出k之前的宽起点为1的矩阵最小和 
     7                 t[k] = sum[j][k] - sum[j-i][k];
     8                 if(k > 1) t[k] = Min(t[k],t[k - 1]);
     9             }
    10             int cur = erfen(j - i + 1,j);
    11             ans = Max(ans,cur);
    12         }
    13     }
    14 
    15     put(ans);

这个t数组在check的时候有妙用，它表示在k之前的宽起点为1的最小矩阵和 ，注意起点是1

看check与二分部分：

1 bool check(int up,int down,int mid){
     2     for(int i = mid;i <= m; ++i){
     3         long long s = sum[down][i] - sum[up - 1][i];
     4         if(s - t[i - mid] > 0) return 1;//如果有宽度大于等于mid的矩和大于零 
     5     }
     6     return 0;
     7 }
     8 
     9 int erfen(int up,int down){
    10     int l = 1,r = m,ans = 0;
    11     while(l <= r){
    12         int mid = (l + r) >> 1;
    13         if(check(up,down,mid)) ans = mid,l = mid + 1;
    14         else r = mid - 1;
    15     }
    16     return ans * (down - up + 1);
    17 }

在check函数中s是宽的起点为1，长度为i的矩阵的和，s - t\[i - mid\]便可以表示宽以i结尾，长度大于等于mid的矩阵的最大和，直接判断是否大于零，就可以返回了

（是不是很妙）

## 满分代码 ##

1 /*****************************
     2 User：Mandy.H.Y
     3 Language:c++
     4 Problem:luogu1565
     5 Algorithm: 
     6 *****************************/
     7 
     8 #include<bits/stdc++.h>
     9 #define Max(x,y) ((x) > (y) ? (x) :(y))
    10 #define Min(x,y) ((x) < (y) ? (x) :(y))
    11 
    12 using namespace std;
    13 
    14 const int maxn = 205;
    15 
    16 int n,m;
    17 long long t[maxn]; 
    18 long long sum[maxn][maxn];
    19 
    20 char *TT,*mo,but[(1 << 15) + 2];
    21 #define getchar() ((TT == mo && (mo = ((TT = but) + fread(but,1,1 << 15,stdin)),TT == mo)) ? -1 : *TT++)
    22 template<class T>inline void read(T &x){
    23     x = 0;char ch = getchar();bool flag = 0;
    24     while(!isdigit(ch)) flag |= ch == '-',ch = getchar(); 
    25     while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
    26     if(flag) x = -x; 
    27 }
    28 
    29 template<class T>void putch(const T x){
    30     if(x > 9) putch(x / 10);
    31     putchar(x % 10 | 48);
    32 }
    33 
    34 template<class T>void put(const T x){
    35     if(x < 0) putchar('-'),putch(-x);
    36     else putch(x);
    37 }
    38 
    39 void file(){
    40     freopen("cow.in","r",stdin);
    41 //    freopen("cow.out","w",stdout);
    42 }
    43 
    44 void readdata(){
    45     read(n);read(m);
    46     for(int i = 1;i <= n; ++ i)
    47         for(int j = 1;j <= m; ++ j){
    48             long long x;read(x);
    49             sum[i][j] = sum[i - 1][j] + sum[i][j - 1] 
    50                       - sum[i-1][j-1] + x;
    51         }
    52 }
    53 
    54 bool check(int up,int down,int mid){
    55     for(int i = mid;i <= m; ++i){
    56         long long s = sum[down][i] - sum[up - 1][i];
    57         if(s - t[i - mid] > 0) return 1;//如果有宽度大于等于mid的矩和大于零 
    58     }
    59     return 0;
    60 }
    61 
    62 int erfen(int up,int down){
    63     int l = 1,r = m,ans = 0;
    64     while(l <= r){
    65         int mid = (l + r) >> 1;
    66         if(check(up,down,mid)) ans = mid,l = mid + 1;
    67         else r = mid - 1;
    68     }
    69     return ans * (down - up + 1);
    70 }
    71 
    72 void work(){
    73     int ans = 0;
    74     
    75     for(int i = n;i >= 1; -- i){
        //枚举长 
    76         if(ans > i * m) break;//剪枝 
    77         for(int j = i;j <= n; ++ j){
        //枚举长的下界 
    78             for(int k = 1;k <= m; ++ k){
        //预处理出k之前的宽起点为1的矩阵最小和 
    79                 t[k] = sum[j][k] - sum[j-i][k];
    80                 if(k > 1) t[k] = Min(t[k],t[k - 1]);
    81             }
    82             int cur = erfen(j - i + 1,j);
    83             ans = Max(ans,cur);
    84         }
    85     }
    86 
    87     put(ans);
    88 
    89 } 
    90 
    91 int main(){
    92 //    file();
    93     readdata();
    94     work();
    95     return 0;
    96 }

至此，这份题解算是结束了，但是重要的并不是正解本身，而是得到正解的这个思维过程

转载于:https://www.cnblogs.com/Mandy-H-Y/p/11355861.html

[1590702-20190815151250822-670686825.png]: /images/20211029/bd511d9ba33f4ca580984f42552a7ef7.png
[1590702-20190815115219459-682638813.png]: /images/20211029/b16dfea063b24548b565e23dca7d836b.png