UVA 12265 Selling Land ( Stack Monotonicity )

UVa Online Judge
白訓練指南的一道經典的單調棧好題。思路是先想像我們大致會做一個高度單調遞增的維護，注意到要判斷一個左上角到當前的右下角構成的矩形周長是否足夠優，只需要知道它的高和當前的列的差( 寬 )。由於只有寬是動態增加的，所以只要能不斷的往右長，左邊的左上角一定會遲早超過右邊的任何左上角。這提示了我們要以當前的高+寬做退出棧的依據，並且右邊的退出之前，左邊的是絕對不會退出。一個更高的左上角進棧的部分已解決，那麼接著思考更矮的( 或者相同高的 )進棧，那麼左邊的左上角若是比它高都必須變矮，而且如果有多個，最後只須留最左邊的就行了。實作的部分需要思考一下。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 3;
const int MAXM = 1e3 + 3;
typedef pair<int, int> pii;

int n, m;
char G[ MAXN ][ MAXM ];

int h[ MAXM ];

int rec_cnt[ 4000 + 100 ];
void solve(){
    for(int i = 0; i < n; ++i){
        deque< pii > stk;
        for(int j = 0; j < m; ++j){
            if( G[ i ][ j ] == '#' ){
                stk.clear();
                h[ j ] = 0;
                continue;
            }
            ++h[ j ];
            pii cur = pii( h[ j ], j );
            while( !stk.empty() && stk.back().first >= h[ j ] ){
                cur.second = stk.back().second;
                stk.pop_back();
            }

            if( stk.empty() ||
                cur.first - cur.second > stk.back().first - stk.back().second )
                stk.push_back( cur );

            int pm = 2 * ( stk.back().first + j - stk.back().second + 1 );
            ++rec_cnt[ pm ];
        }
    }
    for(int i = 2; i <= 2 * ( n + m ); i += 2)
        if( rec_cnt[ i ] )
            printf("%d x %d\n", rec_cnt[ i ], i);
}

int main(){
    int T; scanf("%d", &T);
    while( T-- ){
        memset( rec_cnt, 0, sizeof(rec_cnt) );
        memset( h, 0, sizeof(h) );
        scanf("%d%d", &n, &m);
        for(int i = 0; i < n; ++i)
            scanf("%s", G[ i ]);
        solve();
    }
    return 0;
}