UVA 11270 Tiling Dominoes ( 輪廓線DP )

UVa Online Judge
訓練指南上的輪廓線DP基本題。一開始看的時候怎樣都看不懂，沈下來想就懂了。要考慮的是放一個 tile不管橫置還是直擺，以當前那個格子為那個 tile的右下角，這種“結束考慮這個格子"的情況當作狀態。那麼如果上面的格子沒有放東西，我們就被強制只能直擺將上面填滿，否則我們只能橫置或是不放。這個狀態的構造應該也是輪廓線DP的要點，設計得好似乎就有種剪枝的效果。
好巧不巧一開始我也是設 MAXN = 15結果就 TLE了，看了下面的文章才恍然大悟。差幾倍空間，初始化是會有差的，這同時也是為何要做滾動DP吧。
blog.csdn.net

#include <bits/stdc++.h>
using namespace std;
const int MAXNM = 101;
const int MAXN = 11; // SQRT( MAXNM ) -> swap
typedef long long ll;

int n, m;

ll dp[ 2 ][ 1 << MAXN ];

void solve(){
    if( n > m ) swap( n, m );
    memset( dp, 0, sizeof(dp) );
    int t;
    dp[ t = 0 ][ ( 1 << n ) - 1 ] = 1; // 0 - row is border
    for(int i = 0; i < m; ++i){
        for(int j = 0; j < n; ++j){
            memset( dp[ t^1 ], 0, sizeof( dp[ t^1 ] ) );
            for(int k = 0; k < ( 1 << n ); ++k){ // enumerate upper row
                int up = 0, left = 0;
                if( j == 0 || ( k >> j - 1 ) & 1 ) left = 1; // left is occupied
                if( ( k >> j ) & 1 ) up = 1; // up is occupied
                if( up == 0 ) // up is not occupied -> must fill
                    dp[ t^1 ][ k | ( 1 << j ) ] += dp[ t ][ k ];
                if( left == 0 && up == 1 ) // up is occupied AND left is empty -> can fill left
                    dp[ t^1 ][ k | ( 1 << j ) | ( 1 << j - 1 ) ] += dp[ t ][ k ];
                if( up == 1 ) // up is occupied -> have choice not to put tile ending here
                    dp[ t^1 ][ k ^ ( 1 << j ) ] += dp[ t ][ k ];
            }
            t ^= 1;
        }
    }
    printf("%lld\n", dp[ t ][ ( 1 << n ) - 1 ]);
}

int main(){
    while( scanf("%d%d", &n, &m) == 2 )
        solve();
    return 0;
}