n^2的复杂度
#include#include #include #include #define N 5005 using namespace std; int sum[N][N];//sum[i][j]表示 i列到j列都为1时 存在多少这样的行 int a[N][N]; int n, m; int main(){ int i, j, k; memset(a, 0, sizeof(a)); while(~scanf(%d %d,&n,&m)){ for(i = 1;i <= n;i++) {char s[N]; scanf(%s,s); for(j = 1;j <= m;j++) a[i][j] = s[j-1] == '1'; memset(sum[i], 0, sizeof(sum[i])); } for(i = 1;i <= n; i++)//a[i][j]表示 i行j列的位置 →来连续1的个数 for(j = 1;j <= m; j++) a[i][j] = a[i][j] (a[i][j-1] +1) : 0; for(i = 1;i <= n; i++) { for(j = m;j >= 1; j--)if(a[i][j]) { k = j - a[i][j] +1; sum[k][j] ++; j = k; } } for(i = 1;i <=m ;i++) { for(j = m; j>=i; j--) sum[i][j] += sum[i][j+1]; } for(j = 1;j <= m; j++) { for(i = 1; i <= j; i++) sum[i][j] += sum[i-1][j]; } int ans = 0; for(i = 1;i <= m; i++) for(j = i;j <= m; j++) ans = max(ans, sum[i][j]*(j-i+1)); printf(%d ,ans); } return 0; } /* 1 1 1 2 2 10 11 4 3 100 011 000 101 11 16 0111110101100011 1000101100010000 0010110110010101 0110110010110010 0011101101110000 1001100011010111 0010011111111000 0100100100111110 1001000000100111 0110000011001000 1011111011010000 */