読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


SRM 383 Div1 Medium FloorBoards

問題

1x1のタイル、もしくは1x1の障害物で構成されたサイズが10x10以下の部屋が与えられる。この部屋を1xNの棒で敷き詰めたい(Nは任意の正整数)。棒は部屋の幅もしくは奥行きに対して平行にしか置くことができず、一つのタイルに対して重複して置くことはできない。また障害物に触れる、もしくはまたがるように置くことはできない。与えられた部屋に対して棒を敷き詰めるときもっとも数が少ないように置くときの最小数を求めよ。
部屋の初期状態はvector roomであたえられ、room[i][j]が'.'はその場所がタイル、'#'ならその場所が障害物である。

やりかた

bitDP。
棒は縦か横にしておくことができる。
縦に置く場合は今考えている行に対してひとつ前の行の同じ場所が縦方向に並べて置いてあれば棒の数を増やさずに今の行に縦置きにできる。そしてもし横置きになっていれば置く棒の数は増えるが縦置きにできる。
横置きの場合は今見ている場所の左右の場所が横置きになっているかを考慮すれば置く棒の数が増えるもしくは増えずに横置きできるかのは判断ができる。
まとめると今見ている行に対して置く棒の数が増えるか増えないかはひとつ前の行か今の行の情報があれば十分ということになる。
そうすればひとつ前の行の状態と今の行の状態を全列挙してそれにたいして増える棒の数を記録していくようなbitDPを書くことができる。

以下ソース。

int dp[1 << 11][11];

class FloorBoards {
public:
  int layout(vector <string> room) {
    int N = room.size(), M = room[0].size();
    for(int i = 0; i < 1 << 11; i++)
      for(int j = 0; j < 11; j++) dp[i][j] = INF;

    dp[0][0] = 0;
    for(int i = 0; i < N; i++){
      for(int S = 0; S < 1 << M; S++){
	for(int T = 0; T < 1 << M; T++){
	  int C = S;
	  if(i == 0) C = 0;
	  
	  int bar = 0;
	  for(int j = 0; j < M; j++){
	    if(room[i][j] == '#') continue; //今見ている場所が障害物ならそもそも無視
	    if(T >> j & 1){//今見ているタイルに縦置きの棒を置く場合
	      if(i == 0 || room[i - 1][j] == '#' || !(C >> j & 1))
		bar++;
	    }else{//横置きの棒を置く場合
	      if(j == 0 || room[i][j - 1] == '#' || (T >> (j - 1) & 1))
		bar++;
	    }
	  }
	  dp[T][i + 1] = min(dp[T][i + 1], dp[C][i] + bar);
	}
      }
    }
    int ans = INF;
    for(int i = 0; i < 1 << 11; i++) ans = min(ans, dp[i][N]);
    return ans;
  }
};
しょげないでよBaby 眠れば治る