问题：http://acm.hdu.edu.cn/showproblem.php?pid=2830
Matrix Swapping II
Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 626 Accepted Submission(s): 429
Problem Description
Given an N * M matrix with each entry equal to 0 or 1. We can find some rectangles in the matrix whose entries are all 1, and we define the maximum area of such rectangle as this matrix’s goodness.
We can swap any two columns any times, and we are to make the goodness of the matrix as large as possible.
Input
There are several test cases in the input. The first line of each test case contains two integers N and M (1 ≤ N,M ≤ 1000). Then N lines follow, each contains M numbers (0 or 1), indicating the N * M matrix
Output
Output one line for each test case, indicating the maximum possible goodness.
Sample Input
3 4 1011 1001 0001 3 4 1010 1001 0001
Sample Output
4 2 Note: Huge Input, scanf() is recommended.
Source
问题描述：给一个由0,1构成的矩阵，在这个矩阵内求一个矩形使它内部每一个点都是 1，并且要求1的个数最多，任意两列可以交换，次数不限。
解决方案: 根据任意两列位置可以交换出发，寻找突破口，单独对一行来考虑，由于列可以交换，我们记住每一行的每一列从这一行开始往上最多连续含1的个数（简单dp)，然后再对这一行排序，从而求出以这一行为底的满足条件的矩形含1的最大个数。扫描完所有行后，可以得到满足条件的最大值。
本题难点：由于每一列都在变，要转换思路，对每一行来考虑。
总结：在变之中，结合题意寻找不变的，think out of the box. 这点很关键，转换角度想问题，思考思考。
#include<iostream>
#include<algorithm>
using namespace std;
int dp[1100][1100],hi[1100];
int Max(int a,int b)
{
return a>b?a:b;
}
int main()
{
int i,j,n,m,ans;
char temp;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,0,sizeof(dp));
getchar();
for(i=1,ans=0;i<=n;i++)
{
memset(hi,0,sizeof(hi));
for(j=1;j<=m;j++)
{
scanf("%c",&temp);
if(temp-'0')
dp[i][j]=dp[i-1][j]+1; //dp[i][j]表示位置为(i,j)从这行开始往上含连续1的个数
hi[j-1]=dp[i][j]; //hi[i]表示该行i+1列往上含连续1的最大个数
}
sort(hi,hi+m); //因为列可以交换，先对它进行排序，
for(j=0;j<m;j++)
{
if(hi[j]==0)
continue;
ans=Max(ans,hi[j]*(m-j)); //从而求出以该行为底,以给高度为宽的满足条件的可能的最大值
}
getchar();
}
printf("%d\n",ans);
}
return 0;
}