codeforces 22B B. Bargaining Table(dp)

题目链接：

codeforces 22B

题目大意：

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

题目分析：

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

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 30

using namespace std;

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 );
    }
}