HDU 2830 動態規劃(DP) Matrix Swapping II

分析：掃描每一行，以該行作為底，用dp存放每一列1達到的高度，然後將高度排序(當然，不能直接對dp排序，因為掃下一行的有用)，很容易就能找出最大的面積．最後就可以找出整體的最大值了！

[cpp]
#include<iostream>  
#include<string>  
#include<cstring>  
#include<algorithm>  
 
using namespace std; 
const int maxn=1005; 
 
int work(int g[],int m){ 
    int dp[maxn]; 
    for(int i=0;i<m;++i)dp[i]=g[i]; 
    sort(dp,dp+m); 
    int ret=0; 
    for(int i=m-1;i>=0;--i) 
        ret=max(ret,dp[i]*(m-i)); 
    return ret; 
} 
 
int main(){ 
    int n,m; 
    while(cin>>n>>m){ 
        string map[maxn]; 
        for(int i=0;i<n;++i) 
            cin>>map[i]; 
        int dp[maxn];///存放高度  
        int ans=0; 
        memset(dp,0,sizeof(dp)); 
        for(int i=0;i<n;++i){ 
            for(int j=0;j<m;++j) 
                if(map[i][j]=='1')dp[j]++; 
                else dp[j]=0; 
            ans=max(ans,work(dp,m)); 
        } 
        cout<<ans<<endl; 
    } 
    return 0; 
} 

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>

using namespace std;
const int maxn=1005;

int work(int g[],int m){
    int dp[maxn];
    for(int i=0;i<m;++i)dp[i]=g[i];
    sort(dp,dp+m);
    int ret=0;
    for(int i=m-1;i>=0;--i)
        ret=max(ret,dp[i]*(m-i));
    return ret;
}

int main(){
    int n,m;
    while(cin>>n>>m){
        string map[maxn];
        for(int i=0;i<n;++i)
            cin>>map[i];
        int dp[maxn];///存放高度
        int ans=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;++i){
            for(int j=0;j<m;++j)
                if(map[i][j]=='1')dp[j]++;
                else dp[j]=0;
            ans=max(ans,work(dp,m));
        }
        cout<<ans<<endl;
    }
    return 0;
}