HDU 2830 Matrix Swapping II

悠悠 2022-04-16 06:25 131阅读 0赞

## 原题目链接：[HDU2845][] ##

--------------------

## 分类 ##

HDU 动态规划 贪心

--------------------

## 题意 ##

给我们一个矩阵，问我们最大全1矩阵的面积。注意矩阵的每一列都可以交换。  
即[HDU1505][] [HDU1506][] 的升级版

--------------------

## 想法 ##

dp\[i\]\[j\] : 从a\[i\]\[j\]往下有多少个1  
例如 ：  
a：  
1011  
1001  
0001  
dp：  
2013  
1002  
0001  
然后每次对一行进行排序例如：第一行是 3210

--------------------

## 代码 ##

421ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/18 */
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1111;
    char a[maxn][maxn];
    int dp[maxn][maxn];
    
    /* dp[i][j] : 从a[i][j]往下有多少个1 例如 ： a： 1011 1001 0001 dp： 2013 1002 0001 然后每次对一行进行排序例如：第一行3210 其他相似：HDU1505 HDU1506 */
    
    int n, m;
    
    bool cmp(int a,int b)
    { 
    	return a > b;
    }
    
    int main()
    { 
    	while(cin >> n >> m)
    	{ 
    		memset(dp, 0, sizeof(dp));
    		for(int i =1;i <= n;i++)
    		{ 
    			scanf("%s",a[i]+1);
    		}
    		for(int j = 1;j <= m;j++)
    		{ 
    			for(int i = n;i >=1;i--)
    			{ 
    				if(a[i][j] == '1'){ 
    					dp[i][j] = dp[i+1][j] + 1;
    				}else{ 
    					dp[i][j] = 0;
    				}
    			}
    		}
    		for(int i=1;i<=n;i++){ 
    			for(int j=1;j<=m;j++){ 
    				cout << dp[i][j] ;
    			}
    			cout << endl;
    		} 
    		int ans = 0;
    		for(int i = 1;i <= n;i++)
    		{ 
    			int res = 0;
    			sort(dp[i]+1, dp[i]+m+1, cmp);
    			for(int j = 1;j <= m;j++)
    			{ 
    				res = max(res, dp[i][j] * j);
    			}
    			ans = max(ans, res);
    		}
    		printf("%d\n",ans);
    	}
    }

--------------------

[HDU2845]: http://acm.hdu.edu.cn/showproblem.php?pid=1069
[HDU1505]: http://acm.hdu.edu.cn/showproblem.php?pid=1505
[HDU1506]: http://acm.hdu.edu.cn/showproblem.php?pid=1506