HDU 2830 动态规划(DP) Matrix Swapping II

分析：扫描每一行，以该行作为底，用dp存放每一列1达到的高度，然后将高度排序(当然，不能直接对dp排序，因为扫下一行的有用)，很容易就能找出最大的面积．最后就可以找出整体的最大值了！

[cpp]
#include
#include
#include
#include

using namespace std;
const int maxn=1005;

int work(int g[],int m){
int dp[maxn];
for(int i=0;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 cin>>map[i];
int dp[maxn];///存放高度
int ans=0;
memset(dp,0,sizeof(dp));
for(int i=0;i for(int j=0;j if(map[i][j]=='1')dp[j]++;
else dp[j]=0;
ans=max(ans,work(dp,m));
}
cout< }
return 0;
}

#include
#include
#include
#include

using namespace std;
const int maxn=1005;

int work(int g[],int m){
int dp[maxn];
for(int i=0;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 cin>>map[i];
int dp[maxn];///存放高度
int ans=0;
memset(dp,0,sizeof(dp));
for(int i=0;i for(int j=0;j if(map[i][j]=='1')dp[j]++;
else dp[j]=0;
ans=max(ans,work(dp,m));
}
cout< }
return 0;
}