Codeforces Round #139 (Div. 2) C : Barcode

問題概要

H*W(H,W<1000)の01行列が与えられる。各列を0か1に揃えて、また横に連続する0(or1)の長さがX以上Y以下になるようにしたい。必要な反転回数を最小化する問題。

解法

列を全部0or1にするコストを前計算しておく。後は今見ている列と今の列の色と直前の連続する長さを状態にとって簡単なDPに落ちる。W

acceptされたコード

#include <cstdio>
using namespace std;

const int INF = int(1.05e9); 
const int MAX_N = 1000;
int H, W, X, Y;

int as[MAX_N];
char board[MAX_N][MAX_N + 1];

template<typename numType>
inline bool updateMin(numType& old, const numType& test) {
	if (old > test) {
		old = test;
		return true;
	}
	return false;
}

void init() {
	scanf("%d%d%d%d", &H, &W, &X, &Y);
	for (int i = 0; i < H; ++i) {
		scanf(" %s ", board[i]);
	}
}

int solve() {
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			as[j] += (board[i][j] == '#' ? 1 : 0);
		}
	}

	static int opt[MAX_N + 1][MAX_N + 2][2];
	for (int i = 0; i <= MAX_N; ++i) {
		for (int j = 0; j <= MAX_N + 1; ++j) {
			for (int k = 0; k < 2; ++k) {
				opt[i][j][k] = INF;
			}
		}
	}

	opt[0][0][0] = opt[0][0][1] = 0;
	for (int i = 0; i < W; ++i) {
		for (int j = 0; j <= W; ++j) {
			for (int k = 0; k < 2; ++k) {
				if (X <= j && j <= Y) {
					updateMin(opt[i+1][1][k^1], opt[i][j][k] + (k == 0 ? H - as[i] : as[i]));
				}
				updateMin(opt[i+1][j+1][k], opt[i][j][k] + (k == 0 ? as[i] : H - as[i]));
			}
		}
	}

	int ans = INF;
	for (int i = X; i <= Y; ++i) {
		for (int k = 0; k < 2; ++k) {
			updateMin(ans, opt[W][i][k]);
		}
	}

	return ans;
}

int main() {
	init();
	printf("%d\n", solve());
	return 0;
}