题意:给你个矩阵,里面只有0和1,让你找到最大的只有0的方阵.输出其面积(0的个数) 思路:是个DP,dp[i][j]表示i行j列作为矩阵右下角时的最大矩阵面积.把矩阵扫一遍记录一下dp的最大值就是结果了.状态转移方程还是挺好写的(懒~) 吐槽:结果不加\n给你PE(-_-)
代码:
#include <algorithm> #include <iostream> #include <cstdio> #include <stack> #include <vector> #include <string> #include <cstring> #include <cmath> #include <queue> #include <set> #include <map> #include <list> #include <ctime> using namespace std; #define ll long long #define ld long double #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define EXP 1e-8 #define MOD 1000000007 #define N 50005 #define random(x) rand()%x+1 inline int next_int() { char c; while(c = getchar(), c < '0' || c > '9'); int r = c-'0'; while(c = getchar(), c >= '0' && c <= '9') r = r*10+c-'0'; return r; } int h, w; int dp[2000][2000]; int arr[2000][2000]; int tmp; int ans = 0; int main() { #ifdef Wang_Zhifeng freopen("in.txt", "r", stdin); #endif scanf("%d%d", &h, &w); for(int i = 1; i <= h; ++i) { for(int j = 1; j <= w; ++j) { scanf("%d", &arr[i][j]); } } for(int i = 1; i <= h; ++i) { for(int j = 1; j <= w; ++j) { if(arr[i][j]==0) { tmp = min(dp[i][j-1], dp[i-1][j]); if(dp[i][j-1]==dp[i-1][j]) { if(arr[i-tmp][j-tmp]==0) { dp[i][j] = tmp+1; } else { dp[i][j] = tmp; } } else { dp[i][j] = tmp+1; } } else { dp[i][j] = 0; } ans = max(ans, dp[i][j]); } } printf("%d\n", ans*ans); return 0; }