3039: 玉蟾宮

Time Limit:?2 Sec??Memory Limit:?128 MB
Submit:?753??Solved:?444
[Submit][Status][Discuss]

Description

有一天，小貓rainbow和freda來到了湘西張家界的天門山玉蟾宮，玉蟾宮宮主藍兔盛情地款待了它們，并賜予它們一片土地。
這片土地被分成N*M個格子，每個格子里寫著'R'或者'F'，R代表這塊土地被賜予了rainbow，F代表這塊土地被賜予了freda。
現在freda要在這里賣萌。。。它要找一塊矩形土地，要求這片土地都標著'F'并且面積最大。
但是rainbow和freda的OI水平都弱爆了，找不出這塊土地，而藍兔也想看freda賣萌（她顯然是不會編程的……），所以它們決定，如果你找到的土地面積為S，它們每人給你S兩銀子。

Input

第一行兩個整數N,M，表示矩形土地有N行M列。
接下來N行，每行M個用空格隔開的字符'F'或'R'，描述了矩形土地。

Output

輸出一個整數，表示你能得到多少銀子，即(3*最大'F'矩形土地面積)的值。

Sample Input

5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F

Sample Output

45

HINT

對于50%的數據，1<=N,M<=200
對于100%的數據，1<=N,M<=1000

Source

Poetize4

1057: [ZJOI2007]棋盤制作

Time Limit:?20 Sec??Memory Limit:?162 MB
Submit:?2379??Solved:?1185
[Submit][Status][Discuss]

Description

?

國際象棋是世界上最古老的博弈游戲之一，和中國的圍棋、象棋以及日本的將棋同享盛名。據說國際象棋起源于易經的思想，棋盤是一個8*8大小的黑白相間的方陣，對應八八六十四卦，黑白對應陰陽。而我們的主人公小Q，正是國際象棋的狂熱愛好者。作為一個頂尖高手，他已不滿足于普通的棋盤與規則，于是他跟他的好朋友小W決定將棋盤擴大以適應他們的新規則。小Q找到了一張由N*M個正方形的格子組成的矩形紙片，每個格子被涂有黑白兩種顏色之一。小Q想在這種紙中裁減一部分作為新棋盤，當然，他希望這個棋盤盡可能的大。不過小Q還沒有決定是找一個正方形的棋盤還是一個矩形的棋盤（當然，不管哪種，棋盤必須都黑白相間，即相鄰的格子不同色），所以他希望可以找到最大的正方形棋盤面積和最大的矩形棋盤面積，從而決定哪個更好一些。于是小Q找到了即將參加全國信息學競賽的你，你能幫助他么？

Input

第一行包含兩個整數N和M，分別表示矩形紙片的長和寬。接下來的N行包含一個N * M的01矩陣，表示這張矩形紙片的顏色（0表示白色，1表示黑色）。

Output

包含兩行，每行包含一個整數。第一行為可以找到的最大正方形棋盤的面積，第二行為可以找到的最大矩形棋盤的面積（注意正方形和矩形是可以相交或者包含的）。

Sample Input

3 3
1 0 1
0 1 0
1 0 0

Sample Output

4
6

HINT

N, M ≤ 2000

Source

Solution

懸線法求最大子矩形 ? ?講解

BZOJ3039玉蟾宮 ?就是裸的懸線法

BZOJ1057棋盤制作：

由于要求符合黑白染色的最大子矩形。 直接求顯然非常麻煩，但是我們考慮對問題進行轉化。

如果我們將原矩陣的黑白染色，另黑點0/1全部反轉。那么我們求一個滿足的最大子矩陣就相當于求一個最大的全0/1子矩陣（思考一下還是很容易想到的）

這樣我們懸線法兩次即可。

另一個問題就是最大子正方形。 考慮最大子正方形一定是包含在某個有效的極大子矩形中的，所以我們把所有的有效的極大子矩形中的長寬的較短邊取一個最大，那么最大子正方形一定是這個長度的平方

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int N,M,a[1010][1010],l[1010][1010],r[1010][1010],h[1010][1010],ans;
char c[1];
int main()
{scanf("%d%d",&N,&M);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)scanf("%s",c),a[i][j]=c[0]=='F';for (int i=1; i<=N; i++){for (int j=1,x=0; j<=M; j++)if (a[i][j]) l[i][j]=x; else l[i][j]=0,x=j;for (int j=M,x=M+1; j>=1; j--)if (a[i][j]) r[i][j]=x; else r[i][j]=M+1,x=j;}for (int i=1; i<=M+1; i++) r[0][i]=M+1;for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (a[i][j])h[i][j]=h[i-1][j]+1,l[i][j]=max(l[i][j]+1,l[i-1][j]),r[i][j]=min(r[i][j]-1,r[i-1][j]);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (a[i][j]) ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]);printf("%d\n",ans*3);return 0;
}

BZOJ-3039

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 2010
int N,M,a[MAXN][MAXN],l[MAXN][MAXN],r[MAXN][MAXN],h[MAXN][MAXN],ans,x;
int main()
{scanf("%d%d",&N,&M);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)scanf("%d",&a[i][j]);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if ((i+j)&1) a[i][j]^=1;for (int i=1; i<=N; i++){for (int j=1,x=0; j<=M; j++)if (a[i][j]) l[i][j]=x; else l[i][j]=0,x=j;for (int j=M,x=M+1; j>=1; j--)if (a[i][j]) r[i][j]=x; else r[i][j]=M+1,x=j;}for (int i=1; i<=M+1; i++) r[0][i]=M+1;for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (a[i][j])h[i][j]=h[i-1][j]+1,l[i][j]=max(l[i][j]+1,l[i-1][j]),r[i][j]=min(r[i][j]-1,r[i-1][j]);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (a[i][j]) ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]),x=max(x,min((r[i][j]-l[i][j]+1),h[i][j]));memset(h,0,sizeof(h));for (int i=1; i<=N; i++){for (int j=1,x=0; j<=M; j++)if (!a[i][j]) l[i][j]=x; else l[i][j]=0,x=j;for (int j=M,x=M+1; j>=1; j--)if (!a[i][j]) r[i][j]=x; else r[i][j]=M+1,x=j;}for (int i=1; i<=M+1; i++) r[0][i]=M+1;for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (!a[i][j])h[i][j]=h[i-1][j]+1,l[i][j]=max(l[i][j]+1,l[i-1][j]),r[i][j]=min(r[i][j]-1,r[i-1][j]);for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (!a[i][j]) ans=max(ans,(r[i][j]-l[i][j]+1)*h[i][j]),x=max(x,min((r[i][j]-l[i][j]+1),h[i][j]));printf("%d\n%d\n",x*x,ans);return 0;
}

BZOJ-1057

水題就不一一發了......

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5910280.html

總結

以上是生活随笔為你收集整理的【BZOJ-30391057】玉蟾宫棋盘制作 悬线法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。