程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1057 ZJOI 2007 棋盤制作 DP+懸線法

BZOJ 1057 ZJOI 2007 棋盤制作 DP+懸線法

編輯:C++入門知識

BZOJ 1057 ZJOI 2007 棋盤制作 DP+懸線法


題目大意:給出一個由01形成的矩陣,問這個矩陣中最大面積的正方形和矩形,其中任意一個方塊相鄰的都是不同的格子。

 

思路:其實吧所有(i + j)&1的位置上的數字異或一下,就變成都是0或者都是1的最大正方形和矩形了。第一問就是水DP,第二問可以單調棧或者懸線。都很好寫。

 

CODE:
 

#include 
#include 
#include 
#include 
#define MAX 2010
using namespace std;

int m,n;
int src[MAX][MAX];
int f[MAX][MAX];

int up[MAX][MAX],_left[MAX][MAX],_right[MAX][MAX];

int main()
{
	cin >> m >> n;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j) {
			scanf("%d",&src[i][j]);
			if((i + j)&1)
				src[i][j] ^= 1;
		}
	int ans = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(src[i][j]) {
				f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1;
				ans = max(ans,f[i][j]);
			}
	memset(f,0,sizeof(f));
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(!src[i][j]) {
				f[i][j] = min(f[i - 1][j - 1],min(f[i - 1][j],f[i][j - 1])) + 1;
				ans = max(ans,f[i][j]);
			}
	cout << ans * ans << endl;
	ans = 0;
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j)
			_left[i][j] = src[i][j] ? _left[i][j - 1] + 1:0;
		for(int j = n; j; --j)
			_right[i][j] = src[i][j] ? _right[i][j + 1] + 1:0;
	}
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(src[i][j] && src[i - 1][j]) {
				up[i][j] = up[i - 1][j] + 1;
				_left[i][j] = min(_left[i][j],_left[i - 1][j]);
				_right[i][j] = min(_right[i][j],_right[i - 1][j]);
				ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1));
			}
	memset(_left,0,sizeof(_left));
	memset(_right,0,sizeof(_right));
	memset(up,0,sizeof(up));
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j)
			_left[i][j] = src[i][j] ? 0:_left[i][j - 1] + 1;
		for(int j = n; j; --j)
			_right[i][j] = src[i][j] ? 0:_right[i][j + 1] + 1;
	}
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			if(!src[i][j] && !src[i - 1][j]) {
				up[i][j] = up[i - 1][j] + 1;
				_left[i][j] = min(_left[i][j],_left[i - 1][j]);
				_right[i][j] = min(_right[i][j],_right[i - 1][j]);
				ans = max(ans,(_left[i][j] + _right[i][j] - 1) * (up[i][j] + 1));
			}
	cout << ans << endl;
	return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved