題目大意:給出一個由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; }