SRM 383 500pt: FloorBoards

問題概要

H*W(H,W<10)のボードがあり、各マスは空きか何かが埋まっている。空きのマスだけを長方形の板(幅1、長さは任意)でカバーしたい。ただし板はオーバーラップしてはならない。必要な板の最小枚数を求める問題。

考えたこと

• 何か最大流の匂いがするような。
• でもサイズ小さいし、ビットDP？
• コストの計算に上の列の情報がいるから前の列と今の列で2重にビットを回すのか。
• 計算量がH*2^(2*W)*Wでちょっと多い。2^20 * 100を計算すると10^8。ギリギリ間に合うか？
• 書き始める。気をつけるべきは、余計な工夫をしないこと。バグの温床になるし、最大ケースのテストが面倒になる。
• 向こうで最大ケースが1sちょい。投げたら無事通った。

practiceで通したコード

計算量O(H*2^(2*W)*W)。

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_W = 10;
const int INF = 1<<29;
int dp[MAX_W][1<<MAX_W];

struct FloorBoards {

	int layout(vector <string> room) {
		int H = room.size(), W = room[0].size();

		//初期化
		for(int i=0; i<H; i++){
			fill(dp[i], dp[i] + (1<<W), INF);
		}

		//ビットDP
		for(int i=0; i<H; i++){
			for(int bit1 = 0; bit1 < (1<<W); bit1++){ //bit1: 上の列の組み合わせ
				for(int bit2 = 0; bit2 < (1<<W); bit2++){ //bit2: 今の列の組み合わせ
					int cost = (i==0 ? 0 : dp[i-1][bit1]);
					for(int j=0; j<W; j++)if(room[i][j] == '.'){
						if((bit2>>j)&1){ //横に置く場合
							if(j==0 || room[i][j-1] == '#' || ((bit2>>(j-1))&1)==0){
								cost++;
							}
						}
						else{ //縦に置く場合
							if(i==0 || room[i-1][j] == '#' || ((bit1>>j)&1)==1){
								cost++;
							}
						}
					}
					dp[i][bit2] = min(dp[i][bit2], cost);
				}
			}
		}

		return *min_element(dp[H-1], dp[H-1] + (1<<W));
	}

};