hdu 2830:Matrix Swapping II（简单DP）

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.

题解：哎，又是一道DP题

感觉很简单的亚子，但是开始就偏偏没有想到，看来DP得好好学学啊，重点得找准状态转移方程

由于不管怎么换，锁定一个列，那么该列的元素是一直不变

的，多以可以针对这个，用dp[i]表示该被锁定的列中，连续到第

i行有几个1。

打出上面的dp表，由于列可以无限交换，所以将这一行的dp从

大到小排列后，temp1=dp[1]*1,temp2=dp[2],*2,temp3=dp[3]*3,

temp4=dp[4]*4，……，那么max(temp)就是这一行中的ans。对所有行

进行这个，就可以求出整个图的ans。

于是代码就是：

/**简单dp*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char mp[1010][1010];     //图
int dp[1010][1010];    //dp数组
int cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=1;i<=n;i++)   //从1开始
            scanf("%s",mp[i]+1);
        for(int j=1;j<=m;j++)
        {
            for(int i=1;i<=n;i++)
            {
                if(mp[i][j]=='1')
                    dp[i][j]=dp[i-1][j]+1;     //状态转移方程
                else
                    dp[i][j]=0;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            sort(dp[i]+1,dp[i]+1+m,cmp);    //排序
            for(int j=1;j<=m;j++)
                ans=max(ans,dp[i][j]*j);    //乘以j是为了求面积，然后求最大值
        }
        printf("%d\n",ans);
    }
    return 0;
}