[TIOJ][最大矩形(形)] 1643 - 建工程＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-11-11 09:22:00| 人2,163| 回0 | 上一篇 | 下一篇

[TIOJ][最大矩形(形)] 1643 - 建工程

推 0 收藏 0 0 站台

Description

你是一家建公司的建工程，你被派做一空地的建策工作。

是一矩形的空地，你必在上面一子矩形作房的地基，而了增加收益，你老希望你能量作地基的子矩形面越大越好。

但是基於安全上的考量，你不能地基覆的域的最大「土硬度差」超 L，意即在地基的「最大土硬度」「最小土硬度」必小於等於 L，

否所建造的房子在突然晃（如生地震）有倒塌的危！
你在事前已得知了空地的土硬度分布。了化，我把矩形的空地切格成 N×M 的等大正方形，

假其中每一正方型中的土硬度都是定值 F_ij，而你只能一子矩形且所的子矩形不得包含不完整的正方形。

立了些件後，你到底最大可以取多大的做地基呢？

Figure 1. 即例入的容，答案灰底的子矩形，A = 3×2 = 6。

Input

本入的只有料，第一行有三整 N、M、L。

接下有 N 行，每一行都有 M 非整代表土硬度 F_ij。

於所有料，保1 ≤ N, M ≤ 1000，0 ≤ L ≤ 20，0 ≤ F_ij ≤ 10⁹。

Output

一整 A 代表至多可以在符合安全的件之下取多大矩形面作地基的。

Sample Input

3 3 1 1 1 1 1 2 3 2 1 1

Sample Output

Source

Skyly & Shik Contest II (Problem D)

先解子，找到 "矩中部元素相同的最大矩形"。
也就是色要相同，找到最大矩形。
接著解大小差值得可能，每一都染成一色 [x, x+L]
因此染色情有 L+1 ，於每可能做一次查找元素相同的最大矩形辨答案。

使用堆助找到元素相同的最大矩形，於不同色的全部 pop 出。

照理是 O(NML) 一直 TLE，加入化入後才拿到 AC。

常可能有大。

#include <stdio.h>
#include <stack>
#include <algorithm>
using namespace std;
struct Node {
   int height, position, color;
   Node(int a=0, int b=0, int c=0):
       height(a), position(b), color(c) {}
};
int solve(int n, int h[], int c[]) {
   int ret = 0;
   int i, height, color;
   stack<Node> stk;// <height, position, color>
   Node e;
   h[n] = 0, c[n] = -1;// visual height.
   stk.push(Node(-1, 0, 0));
   for(i = 0; i <= n; i++) {
       height = h[i];
       color = c[i];
       while(stk.size() > 1 && color != stk.top().color) {
           e = stk.top(), stk.pop();
           ret = max(ret, (i - e.position) * e.height);
       }
       e = Node(height, i, color);
       while(height < stk.top().height) {
           e = stk.top(), stk.pop();
           ret = max(ret, (i - e.position) * e.height);
       }
       if(height > stk.top().height)
           stk.push(Node(height, e.position, color));
   }
   return ret;
}
int n, m, L, h[1005], c[1005];
int g[1005][1005], cg[1005][1005];
int maxRectArea(int n, int m, int g[][1005]) {
   int i, j;
   int ret = 0, prev[1005] = {};
   for(i = 0; i < m; i++) {
   &nbp;   for(j = 0; j < n; j++) {
           if(i && g[j][i-1] != g[j][i])
               prev[j] = 0;
           h[j] = ++prev[j], c[j] = g[j][i];
       }
       ret = max(ret, solve(n, h, c));
   }
   return ret;
}
int colorProcess(int L) {
   int cnt = 0;
   int i, j, k;
   int ret = 0;
   for(i = 0; i <= L; i++) {
       for(j = 0; j < n; j++) {
           int *p = g[j];
           for(k = 0; k < m; k++) {
               cg[j][k] = (*p+100-i)/(L+1)*(L+1)+i;
               p++;
           }
       }
       ret = max(ret, maxRectArea(n, m, cg));
   }
   return ret;
}
inline int ReadInt(int *x) {
    static char c, neg;
    while((c = getchar()) < '-')    {if(c == EOF) return EOF;}
    neg = (c == '-') ? -1 : 1;
    *x = (neg == 1) ? c-'0' : 0;
    while((c = getchar()) >= '0')
        *x = (*x << 3) + (*x << 1) + c-'0';
    *x *= neg;
    return 1;
}
int main() {
   int i, j;
   while(scanf("%d %d %d", &n, &m, &L) == 3) {
       for(i = 0; i < n; i++) {
           int *p = g[i];
           for(j = 0; j < m; j++) {
               ReadInt(&p[j]);
           }
       }
       int ret = 0;
       ret = colorProcess(L);
       printf("%d\n", ret);
   }
   return 0;
}