POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

• 第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
• 第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

• 第一列狀態D1=(00100001100)2
• 第二列狀態D2=(11010010000)2
• 第三列狀態D3=(00100001001)2
• 其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

    定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

    為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

    另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

    最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。

UVa 11218 KTV

題意：
    總共有9個人(編號1~9)要分成3組唱歌，每組3個人，每個人只能唱一次。第一行N表示底下有N種組合，每種組合a,b,c,s，前三個是人員編號，s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌，並且使得分數的和最高，輸出該分數，如果找不到組合滿足大家都能唱到歌則輸出-1。

想法：
    bitmask，(1<<9)-1表示所有人都唱的到歌的狀態，二進位來看就是(111111111)2，dp[i]=j表示在狀態i的情況下最高分數為j，因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
    用dfs來枚舉不同組合，當人員沒有重複的時候才能將兩個狀態合併在一起，例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2，並去更新dp[(000111111)2]的分數，不斷更新所有可能的合併來枚舉所有情況。

UVa 10651 Pebble Solitaire

題意：
    跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。

想法：
    想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。

POJ 1753 Flip Game

想法：
    Bit運算，16位來表示棋盤的情況，16個0表示全白，16個1表示全黑。用BFS演算法，從一開始的情況開始出發，直到變成全白或全黑為止，或是無法變成全白或全黑。