網頁

2014年5月30日 星期五

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]來紀錄答案,如果重複的題目就直接輸出即可。