hdu2380（dp,最大矩形面积）

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.

题意：任意两列可以交换，求最大的矩形面积。

题解：用一个二维数组存储每一个点往上最多有多少个连续的1。然后对每一个行进行考虑，新开一个数组存每一行的纵列数，从大到小排序，那么把每一个点长乘宽后，取最大面积即可（因为已经从小到大已经排好了，所以在每个点之前的都可以乘进来，比如第4个数纵列有4 个，那么我们面积就可以4*4了）

最后取每一列的最大值即可。

ac代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <cstdlib>
#include <queue>
#include<iomanip>
using namespace std;
int s[1005];
int p[1005][1005];
bool cmp(int a, int b)
{
	return a > b;
}
int main()
{
	int n, m,k,ant,sum;
	char a;
	while (cin >> n >> m)
	{
		memset(p, 0, sizeof(p));
		for (int i = 1; i <= n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				scanf(" %c",&a);
				if (a=='1')p[i][j] = p[i - 1][j] + 1;
				
			}
		}sum = 0;
		for (int i = 1; i <= n; i++)
		{
			k = 1; ant = 0; 
			for (int j = 0; j < m; j++)
				s[j] = p[i][j];
			sort(s, s + m, cmp);
			for (int g = 0; g < m; g++)
			{
			
				ant = max(ant, s[g] * k);
				k++;
			}sum = max(sum, ant);
		}cout << sum << endl;
	}
}