效果好企业营销型网站建设/数据交换平台

Codeforces Round #221 (Div. 1) B:http://codeforces.com/problemset/problem/375/B

题意：给你一个n*m的0,1矩阵，你可以交换一些行，求一个最大子矩阵的面积，这个子矩阵全部包含1.

题解：看标签是数据结构，怎么想，也不知道用数据结构怎么搞。最后想到是求面积，面积不就是l*d，只要确定了了l和d，面积就出来了，于是我想到了枚举l和d。这里要先处理出来一些东西，dp[j][i]表示(i,j)的右边的有多少个连续的1，包括(i，j)，可以这么想，矩阵的左边一定出现在那一列，所以可以枚举列，对于固定左边来说，也就是起点固定了，那么狠容易想到，，要把连续1多的放在一起，所以要对该列进行排个序，然后就可以开始枚举，从上到下，因为最上面的是最短的，所以下面构成的面积才是我们想要的。得到最大的面积。表述不是很清晰，还是看代码吧。题解说用基数排序，但是我用了基数排序，发现比类库的排序要慢，也许是数据小的原因吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using  namespace std;
const int N=5004;
int n,m,r[N][N];
char mp[N][N];
bool temp[N];
/*int counts[N],tmp[N];
int maxbit(int x){
    int d=1;
    for(int i=1;i<=n;i++){
        int c=1;
        int p=r[x][i];
        while(p/10){
            p=p/10;
            c++;
        }
        if(c>d)
            d=c;
    }
    return d;
}
void RadixSort(int x){
    int d=maxbit(x);
        int rr=1;
    for(int i=0;i<d;i++){
        for(int j=0;j<10;j++)
            counts[j]=0;
        for(int j=1;j<=n;j++) {
            int k=r[x][j]/rr;
            int q=k%10;
            counts[q]++;
        }
        for(int j=1;j<10;j++){
            counts[j]+=counts[j-1];
        }
        for(int j=n;j>=1;j--)
        {
            int p=r[x][j]/rr;
            int s=p%10;
            tmp[counts[s]-1]=r[x][j];
            counts[s]--;
        }
        for(int j=0;j<n;j++){
            r[x][j+1]=tmp[j];
        }
        rr=rr*10;
    }
}*/
int main(){
    while(~scanf("%d%d",&n,&m)){
        memset(r,0,sizeof(r));
        for(int i=1;i<=n;i++)
             scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++){
                int temp=0;
            for(int j=m;j>=1;j--){
                if(mp[i][j]=='0'){
                    temp=0;
                }
                else
                   temp++;
                 r[j][i]=temp;
            }
        }
        int ans=0;
       for(int i=1;i<=m;i++){
            //RadixSort(i);
            sort(r[i]+1,r[i]+n+1);
         for(int j=1;j<=n;j++){
             ans=max(ans,r[i][j]*(n-j+1));
         }
       }
        printf("%d\n",ans);
    }
}