codeforces 22B B. Bargaining Table(dp)

题目链接:

codeforces 22B

题目大意:

给出一个矩阵,求周长最大的矩形的周长

题目分析:

求出每个点为底的最大的高度(0),然后枚举右下角,再枚举矩形的高度,,然后算取长度,进而算取周长即可。

AC代码:;int n,m;char a[MAX][MAX];int h[MAX][MAX];int l[MAX][MAX];int r[MAX][MAX];int main ( ){while ( ~scanf ( “%d%d” , &n , &m ) ){for ( int i = 0 ; i < n ; i++ )scanf ( “%s” , a[i] );for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ ){if ( a[i][j] == ‘1’ ){h[i][j] = 0;continue;}if ( i == 0 || a[i-1][j] == ‘1’ )h[i][j] = 1;else h[i][j] = h[i-1][j] + 1;}int ans = 0;for ( int i = 0 ; i < n ; i++ )for ( int j = 0 ; j < m ; j++ )for ( int k = 1 ; k <= h[i][j] ; k++ ){int l = j;while ( l >= 0 && h[i][l] >= k )l–;ans = max ( ans , (j-l)+k );}printf ( “%d\n” , ans*2 );}}

从起点,到尽头,也许快乐,或有时孤独,

codeforces 22B B. Bargaining Table(dp)

相关文章:

你感兴趣的文章:

标签云: