首页 > 代码库 > bzoj1057 [ZJOI2007]棋盘制作
bzoj1057 [ZJOI2007]棋盘制作
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1057
【题解】
把网格图黑白染色,把原来的颜色异或黑白染色的颜色,就变成求最大0/1子矩形/正方形
以最大全1子矩形为例。
我们设a[i,j]表示第i行第j个之前有多少个连续的1。
那么我们维护a单调上升的单调栈
每次加入一个元素,如果比前面大等直接做,小的话更新答案,(这个元素到前面那个元素的一大段都能达到前面那个元素的a值)
注意更新完答案,要更新位置值,这个值为这次更新最后一个出栈的那个位置。
(因为我可以连续更新到那里啊。。这一大段都行)
所以就行了。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 2e3 + 10; const int mod = 1e9+7; # define RG register # define ST static int n, m, ans1, ans2; int mp[M][M], a[M][M]; int stn; struct pa { int x, h; pa() {} pa(int x, int h) : x(x), h(h) {} }st[M]; inline int sqr(int x) { return x*x; } inline void doit(int pos, int H) { int pre = pos; while(stn && st[stn].h > H) { ans1 = max(ans1, (pos-st[stn].x)*st[stn].h); ans2 = max(ans2, sqr(min(pos-st[stn].x, st[stn].h))); pre = st[stn].x; --stn; } st[++stn] = pa(pre, H); } inline void getans() { for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) if(mp[i][j] == 0) a[i][j] = 0; else a[i][j] = a[i][j-1] + 1; for (int i=1; i<=m; ++i) { stn = 0; for (int j=1; j<=n; ++j) doit(j, a[j][i]); doit(n+1, 0); } } int main() { cin >> n >> m; for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) { scanf("%d", &mp[i][j]); int c = (i+j)&1; mp[i][j] ^= c; } // for (int i=1; i<=n; ++i, cout << endl) // for (int j=1; j<=m; ++j) cout << mp[i][j]; getans(); for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) mp[i][j] ^= 1; getans(); cout << ans2 << endl << ans1 << endl; return 0; }
bzoj1057 [ZJOI2007]棋盘制作
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。