TopCoder SRM 383 Div1 Medium FloorBoards

問題

room[i][j]のグリッドで表されるような長方形の部屋がある。
room[i][j]が'#'であるとき、(i,j)は柱があり、'.'であるとき(i,j)には何もない。

何もないマス全てに板を敷きたい。
板は、幅が1で、長さは自由である。
板は最低で何枚必要か求めよ。
板同士が重なったり、板がグリッドの外にはみでたりしてはならない。

制約条件

roomの行≦10
roomの列≦10

方針

動的計画法による。
dp[i][j][mask]を、i行目まで全て敷いて、i行目はj列まで板を敷いていて、
上一列分の板の向きをビットで表した整数がmaskであるような状態にするために必要な板の最小枚数とする。

(i,j)のマスには板を縦または横にするという2通りの敷き方がある。
板を縦に敷いたとき、一つ上のマスが縦向きならつなげられるので、新たなコストはかからない。
同様に横に敷いたとき、一つ左のマスが横向きならば新たなコストがかからない。

このようにテーブルを更新していくDPにより最適解が求まる。

ソースコード

int h,w;
int dp[11][11][1<<10];

class FloorBoards {
  public:
  int layout(vector <string> room) {
    h=room.size(); w=room[0].size();
    rep(i,h+1)rep(j,w+1)rep(k,1<<w)dp[i][j][k]=inf;
    dp[0][0][0]=0;
    rep(i,h){
      rep(j,w)rep(k,1<<w)rep(l,2){
        int mask=k&~(1<<j)|l<<j, cost=dp[i][j][k]+1;
        if(l==0&&i&&!(k&1<<j)&&room[i-1][j]=='.'||
          l==1&&j&&(k&1<<j-1)&&room[i][j-1]=='.'||
          room[i][j]=='#')cost--;
        dp[i][j+1][mask]=min(dp[i][j+1][mask],cost);
      }
      rep(k,1<<w)dp[i+1][0][k]=dp[i][w][k];
    }
    int ans=inf;
    rep(i,1<<w)ans=min(ans,dp[h][0][i]);
    return ans;
  }
};