欢迎光临散文网 会员登陆 & 注册

Luogu_P4039 【[AHOI2014 JSOI2014]拼图】 题解

2020-01-03 18:48 作者:hnyqwq  | 我要投稿

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发现,可以通过改变这S块拼图的连接次序,使得拼成的N行M列的大矩形中,最大全白子矩形面积变大。现在JYY想知道,怎么拼才能得到最大的全白子矩形呢?请你帮助他计算出最佳的拼接方案。


输入格式


第一行包含一个整数T,代表测试数据的组数,接下来按顺序描述了每组测试数据。


每组测试数据的第一行包含两个整数S和N。


接下来S组输入,第i组对应编号为i的拼图。


在第i组输入中,第一行包含一个整数 Wi ;


接下来N行描述一个N行 Wi 列的0/1矩形;


其中第x行y列为0则表示该拼图对应位置的颜色是白色,反之则为黑色。


输出格式


对于每组数据输出一行包含一个整数ans,表示最大可能的全白色子矩形的面积。


输入输出样例


输入 #1复制

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

输出 #1复制

6

说明/提示


对于100%的数据满足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循环
           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循环
           mp = g[i];
           for(int j = i; j <= n; j++) {   //for循环
               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循环
                   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循环
       s = iread(), n = iread();
       if(n <= 300) subtask1::solve();
       else subtask2::solve();
   }
   return 0;    //不写return 0,成绩return 0
}


提交记录 in 2019-10-10


Luogu_P4039 【[AHOI2014 JSOI2014]拼图】 题解的评论 (共 条)

分享到微博请遵守国家法律