本文共 1949 字，大约阅读时间需要 6 分钟。

题目链接：

题目大意：

给出一个01矩阵，行与行之间可以互换位置，问能够得到最大的全1矩阵的面积。

题目分析：

• 我们有一种模型，就是对于不互换行的01矩阵求最大面积，就是固定子矩阵的右下角，记录h[i][j]就是当前位置的高度，然后向左延展的距离，枚举所有的即可。
• 代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 5007using namespace std;int n,m;char mp[MAX][MAX];int lef[MAX];int h[MAX][MAX];int main ( ){    while ( ~scanf ( "%d%d" , &n , &m ))    {        for ( int i = 1 ; i <= n ; i++ )            scanf ( "%s" , mp[i]+1 );        memset ( h , 0 , sizeof ( h ));        int ans = 0;        for ( int i = 1 ; i <= n ; i++ )        {            for ( int j = 1 ; j <= m ; j++ )            {                if ( mp[i][j] == '0' ) h[i][j] = 0;                else if ( i == 1 || mp[i-1][j]=='0')                    h[i][j] = 1;                else h[i][j] = h[i-1][j]+1;                if ( j == 1 || h[i][j-1] < h[i][j] )                    lef[j] = j;                else lef[j] = lef[j-1];            }            for ( int j = 1 ; j <= m ; j++ )                ans = max ( ans , (j-lef[j]+1)*h[i][j] );        }        printf ( "%d\n" , ans );    }}
      
     
    
   

• 那么对于可以行互换的，我们已经记录每个点能够向左延展的距离,定义状态dp[j][i]代表第j列的第i行的元素向左延展的最远距离，然后我们对这个距离排序，从大到小，每个上面的都可以被下面的拓展，那么依旧是枚举每个右下角，取最大的结果。

AC代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #define MAX 5007using namespace std;int n,m;int dp[MAX][MAX];char mp[MAX][MAX];int main (){    while ( ~scanf ( "%d%d" , &n , &m ))    {        for ( int i = 1 ; i<= n ; i++ )            scanf ( "%s" , mp[i]+1 );        for ( int i= 1 ; i <= n ; i++ )            for ( int j = 1 ; j <= m ; j++ )                if ( mp[i][j] == '1' )                    dp[j][i] = dp[j-1][i]+1;                else dp[j][i] = 0;        int ans = 0;        for ( int i = 1 ; i <= m ; i++ )        {            sort ( dp[i]+1 , dp[i]+n+1 );            for ( int j = n ; j > 0 ; j-- )                ans = max ( ans , dp[i][j]*(n-j+1) );        }        printf ( "%d\n" , ans );    }}
      
     
    
   

转载地址：http://bqvjn.baihongyu.com/