1.【題目鏈接】

題目描述

JYY最近迷上了拼圖游戲。作為一個計算機科學家，JYY有一套黑白色的拼圖，他希望通過合理的拼接，使得拼出的最終圖案中，能包含面積最大的全白色子矩形。JYY一共有S塊拼圖，并且由1到S編號。編號為i的拼圖是一個N行列的方格矩形，每個方格都為黑色或者白色。一開始JYY將他的這S塊拼圖按照編號順序左右相連依次放在桌上拼成了一個N行M列（這里M=\sum(W_i)(1\le i \le SM=∑(Wi)(1≤i≤S）的大矩形。之后JYY發(fā)現(xiàn)，可以通過改變這S塊拼圖的連接次序，使得拼成的N行M列的大矩形中，最大全白子矩形面積變大?，F(xiàn)在JYY想知道，怎么拼才能得到最大的全白子矩形呢？請你幫助他計算出最佳的拼接方案。

輸入格式

第一行包含一個整數(shù)T，代表測試數(shù)據(jù)的組數(shù)，接下來按順序描述了每組測試數(shù)據(jù)。

每組測試數(shù)據(jù)的第一行包含兩個整數(shù)S和N。

接下來S組輸入，第i組對應編號為i的拼圖。

在第i組輸入中，第一行包含一個整數(shù)?Wi?；

接下來N行描述一個N行?Wi?列的0/1矩形；

其中第x行y列為0則表示該拼圖對應位置的顏色是白色，反之則為黑色。

輸出格式

對于每組數(shù)據(jù)輸出一行包含一個整數(shù)ans，表示最大可能的全白色子矩形的面積。

輸入輸出樣例

輸入 #1復制

1
3 4
4
1001
0000
0010
1001
3
000
010
000
011
2
00
10
01
00

輸出 #1復制

6

說明/提示

對于100%的數(shù)據(jù)滿足1\le S,N,W \le 10^5, N\times \sum W_i \le10^5,T\le31≤S,N,W≤105,N×∑Wi≤105,T≤3

2.思路

記m = ∑^w_i

對于n <= 300的情況，暴力O(n^2)枚舉矩形的上下邊界，O(m)計算矩形內的答案。

對于n > 300的情況，暴力O(n)枚舉矩形的上邊界，然后枚舉暴力O(m)枚舉高度（最大全0子矩陣單調棧做法的高度），最后對于每個高度，O(m)計算矩形內的答案。

計算答案的過程是：

枚舉每一個矩形，計算出所有矩形左邊界和右邊界能向內延伸的最大值和次大值，記錄次大值的原因是，如果左邊界右邊界最大值的矩形是同一個矩形，那么就不合法了，就只能用次大值去更新答案。

3.Code

//Happynewyear 2019/1/23 20:23
#include<bits/stdc++.h> ? ? //萬能頭文件
using namespace std;

const int maxn = 305, maxm = 100005;

int s, n, m, pos[maxm];
bitset<maxm> g[maxn], mp;

inline int iread() {
? ?int f = 1, x = 0; char ch = getchar();
? ?for(; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
? ?for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
? ?return f * x;
}

inline int cread() {
? ?char ch = getchar(); for(; ch != '0' && ch != '1'; ch = getchar());
? ?return ch - '0';
}

namespace subtask1 {
? ?void solve() {
? ? ? ?int ans = 0;
? ? ? ?for(int i = 1; i <= s; i++) { ?//for循環(huán)
? ? ? ? ? ?pos[i] = pos[i - 1] + iread();
? ? ? ? ? ?for(int j = 1; j <= n; j++) for(int k = pos[i - 1] + 1; k <= pos[i]; k++)
? ? ? ? ? ? ? ?g[j][k] = cread();
? ? ? ?}
? ? ? ?m = pos[s];
? ? ? ?for(int i = 1; i <= n; i++) { ?//for循環(huán)
? ? ? ? ? ?mp = g[i];
? ? ? ? ? ?for(int j = i; j <= n; j++) { ? //for循環(huán)
? ? ? ? ? ? ? ?mp |= g[j];
? ? ? ? ? ? ? ?for(int k = 1, sum = 0; k <= m; k++) {
? ? ? ? ? ? ? ? ? ?sum = mp[k] ? 0 : sum + 1;
? ? ? ? ? ? ? ? ? ?ans = max(ans, sum * (j - i + 1));
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?int l1 = 0, l2 = 0, lno = 0;
? ? ? ? ? ? ? ?int r1 = 0, r2 = 0, rno = 0;
? ? ? ? ? ? ? ?int sum = 0, full = 0;
? ? ? ? ? ? ? ?for(int k = 1; k <= s; k++) { ? //for循環(huán)
? ? ? ? ? ? ? ? ? ?sum = 0;
? ? ? ? ? ? ? ? ? ?for(int l = pos[k - 1] + 1; l <= pos[k]; l++, sum++)
? ? ? ? ? ? ? ? ? ? ? ?if(mp[l]) break;
? ? ? ? ? ? ? ? ? ?if(sum == pos[k] - pos[k - 1]) {
? ? ? ? ? ? ? ? ? ? ? ?full += sum;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ?if(sum > l1) l2 = l1, l1 = sum, lno = k;
? ? ? ? ? ? ? ? ? ?else if(sum > l2) l2 = sum;
? ? ? ? ? ? ? ? ? ?sum = 0;
? ? ? ? ? ? ? ? ? ?for(int r = pos[k]; r >= pos[k - 1] + 1; r--, sum++)
? ? ? ? ? ? ? ? ? ? ? ?if(mp[r]) break;
? ? ? ? ? ? ? ? ? ?if(sum > r1) r2 = r1, r1 = sum, rno = k;
? ? ? ? ? ? ? ? ? ?else if(sum > r2) r2 = sum;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?ans = max(ans, (((lno == rno) ? max(l1 + r2, l2 + r1) : l1 + r1) + full) * (j - i + 1));
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?printf("%d\n", ans); ? //輸出
? ?}
}

namespace subtask2 {
? ?int f[maxm];

? ?void solve() {
? ? ? ?int ans = 0;
? ? ? ?for(int i = 1; i <= s; i++) {
? ? ? ? ? ?pos[i] = pos[i - 1] + iread();
? ? ? ? ? ?for(int k = 1; k <= n; k++) for(int j = pos[i - 1] + 1; j <= pos[i]; j++)
? ? ? ? ? ? ? ?g[j][k] = cread();
? ? ? ?}
? ? ? ?m = pos[s];
? ? ? ?for(int i = n; i; i--) {
? ? ? ? ? ?for(int j = 1; j <= m; j++) f[j] = g[j][i] ? 0 : f[j] + 1;
? ? ? ? ? ?for(int j = 1; j <= m; j++) {
? ? ? ? ? ? ? ?for(int k = 1, sum = 0; k <= m; k++) {
? ? ? ? ? ? ? ? ? ?sum = f[k] < f[j] ? 0 : sum + 1;
? ? ? ? ? ? ? ? ? ?ans = max(ans, f[j] * sum);
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?int l1 = 0, l2 = 0, lno = 0;
? ? ? ? ? ? ? ?int r1 = 0, r2 = 0, rno = 0;
? ? ? ? ? ? ? ?int sum = 0, full = 0;
? ? ? ? ? ? ? ?for(int k = 1; k <= s; k++) {
? ? ? ? ? ? ? ? ? ?sum = 0;
? ? ? ? ? ? ? ? ? ?for(int l = pos[k - 1] + 1; l <= pos[k]; l++, sum++)
? ? ? ? ? ? ? ? ? ? ? ?if(f[l] < f[j]) break;
? ? ? ? ? ? ? ? ? ?if(sum == pos[k] - pos[k - 1]) {
? ? ? ? ? ? ? ? ? ? ? ?full += sum;
? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ?if(sum > l1) l2 = l1, l1 = sum, lno = k;
? ? ? ? ? ? ? ? ? ?else if(sum > l2) l2 = sum;
? ? ? ? ? ? ? ? ? ?sum = 0;
? ? ? ? ? ? ? ? ? ?for(int r = pos[k]; r >= pos[k - 1] + 1; r--, sum++)
? ? ? ? ? ? ? ? ? ? ? ?if(f[r] < f[j]) break;
? ? ? ? ? ? ? ? ? ?if(sum > r1) r2 = r1, r1 = sum, rno = k;
? ? ? ? ? ? ? ? ? ?else if(sum > r2) r2 = sum;
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?ans = max(ans, (((lno == rno ? max(l1 + r2, l2 + r1) : l1 + r1) + full) * f[j]));
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?printf("%d\n", ans); ? ? //輸出
? ?}
}

int main() {
? ?for(int T = iread(); T; T--) { ? ? ?//for循環(huán)
? ? ? ?s = iread(), n = iread();
? ? ? ?if(n <= 300) subtask1::solve();
? ? ? ?else subtask2::solve();
? ?}
? ?return 0; ? ?//不寫return 0,成績return 0
}

提交記錄 in 2019-10-10