CF：375B - Maximum Submatrix 2 不太像DP

题意：求最小的子矩阵中含1个数最多的子矩阵。

思路：这题也看了好久，反正就是统计长和宽的1的个数，不过因为可能1如果在同一列，但是行不接近的这种情况得处理，所以……就是统计行的1的个数以后再排序嘛……

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 1000002
#define MN 5005
#define INF 1000000007
using namespace std;
typedef long long ll;
int n,m,i,j,sum,a[MN][MN],dp[MN];
char s[MN][MN];
int main()
{
    scanf("%d%d",&n,&m);
    for(i=0;i<n&&scanf("%s",s[i]);i++);
    for(j=m-1;j>=0;j--)
    {
        for(i=0;i<n;i++)
        {
            if(s[i][j]==‘0‘) dp[i]=a[i][j]=0;
            else dp[i]=a[i][j]=a[i][j+1]+1; //每行的1个数
        }
        sort(dp,dp+n,greater<int>());
        for(i=0;i<n;i++) 
            sum=max(sum,dp[i]*(i+1)); //再乘以列数，就相当于长乘以宽了
    }
    cout<<sum<<endl;
    return 0;
}

CF：375B - Maximum Submatrix 2 不太像DP

原文：http://blog.csdn.net/u011466175/article/details/19704257