嘟嘟嘟

正是因?yàn)橛羞@樣的數(shù)據(jù)范圍，解法才比較暴力。

我們假設(shè)取出的長方體常和寬相等，即\(a * a * b\)。這樣我們每次換兩條邊相等，搞三次就行。
那么對于第\(k\)層中的第\((i, j)\)點(diǎn)\((k, i, j)\)，求出以這個(gè)點(diǎn)為右下角的最大完好的正方形f[k][i][j]。這個(gè)可以用倍增求。所以復(fù)雜度為\(O(n ^ 3 logn)\)。
然后\(O(n ^ 2)\)枚舉平面上的每一個(gè)點(diǎn)\((x, y)\)，立體的就是每一豎條，那么對于每一豎條，我們要求的就是\(max \{(i - j + 1) * (min_{t = j} ^ {i} f[t][x][y]) \}\)。這個(gè)求法就是poj 2559了，用單調(diào)遞增棧\(O(n)\)維護(hù)就行。這個(gè)的復(fù)雜度是\(O(n ^ 3)\)的。
所以總復(fù)雜度\(O(n ^ 3 logn)\)。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define In inline typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 155; inline ll read() {ll ans = 0;char ch = getchar(), last = ' ';while(!isdigit(ch)) last = ch, ch = getchar();while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();if(last == '-') ans = -ans;return ans; } inline void write(ll x) {if(x < 0) x = -x, putchar('-');if(x >= 10) write(x / 10);putchar(x % 10 + '0'); }int p, q, r; int _a[3][maxn][maxn][maxn], a[maxn][maxn][maxn];int sum[maxn][maxn][maxn], f[maxn][maxn][maxn]; In int calc(int k, int i, int j) {int L = 1, R = min(i, j);while(L < R){int mid = (L + R + 1) >> 1;int Sum = sum[k][i][j] - sum[k][i - mid][j] - sum[k][i][j - mid] + sum[k][i - mid][j - mid];if(!Sum) L = mid;else R = mid - 1;}return L; } struct Node {int num, len; }st[maxn]; In int solve(int p, int q, int r) {for(int k = 1; k <= r; ++k)for(int i = 1; i <= p; ++i)for(int j = 1; j <= q; ++j){int tp = (a[k][i][j] == 'N' ? 0 : 1);sum[k][i][j] = sum[k][i - 1][j] + sum[k][i][j - 1] - sum[k][i - 1][j - 1] + tp;}for(int k = 1; k <= r; ++k)for(int i = 1; i <= p; ++i)for(int j = 1; j <= q; ++j) f[k][i][j] = calc(k, i, j);int ret = 0, top = 0;for(int i = 1; i <= p; ++i)for(int j = 1; j <= q; ++j){top = 0; f[r + 1][i][j] = 0;for(int k = 1; k <= r + 1; ++k){if(!top || st[top].num < f[k][i][j]) st[++top] = (Node){f[k][i][j], 1};else{int tp = 0;while(top && st[top].num >= f[k][i][j]){ret = max(ret, st[top].num * (st[top].len + tp));tp += st[top--].len;}st[++top] = (Node){f[k][i][j], tp + 1};}}}return ret; }char s[maxn]; int main() {p = read(), q = read(), r = read();for(int j = 1; j <= q; ++j)for(int i = 1; i <= p; ++i){scanf("%s", s + 1);for(int k = 1; k <= r; ++k) _a[0][k][i][j] = _a[1][i][k][j] = _a[2][j][i][k] = s[k];}int ans = 0;memcpy(a, _a[0], sizeof(_a[0]));ans = max(ans, solve(p, q, r));memcpy(a, _a[1], sizeof(_a[1]));ans = max(ans, solve(r, q, p));memcpy(a, _a[2], sizeof(_a[2]));ans = max(ans, solve(p, r, q));write(ans << 2), enter;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/mrclr/p/10400084.html

總結(jié)

以上是生活随笔為你收集整理的[ZJOI2011]礼物的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。