KUPC2012 D : 権力

問題概要

M(<100)個の区間がある。[0, N)を被覆するのに最小いくつ必要か求める問題。

解法

最初に区間を左端でソートしておいて、dp[i][j] = {iまでで、区間[0, j)を被覆するのに最小いくつ必要か}とするとO(N^2*M)で解ける。
真面目にやればO(N*M)でも解ける。
また、動的計画法を持ち出さなくても貪欲でも解ける(蟻本p.47と似てる)。これだとO(M*log M) (ボトルネックはソート)。

acceptされたコード

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
const int MAX_M = 100;
const int INF = 1<<29;

int N, M;
int minNum[MAX_M + 1][MAX_N + 1];
pair<int, int> rs[MAX_N];

void init() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < M; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		--a;
		rs[i] = make_pair(a, b);
	}
}

void solve() {
	sort(rs, rs + M);
	for (int i = 0; i <= M; ++i) {
		fill(minNum[i], minNum[i] + N + 1, INF);
	}
	minNum[0][0] = 0;

	for (int i = 0; i < M; ++i) {
		for (int j = 0; j <= N; ++j) {
			minNum[i+1][j] = min( minNum[i+1][j], minNum[i][j]);
			if (rs[i].first <= j) {
				for (int k = j; k <= rs[i].second; ++k) {
					minNum[i+1][k] = min( minNum[i+1][k], minNum[i+1][j] + 1 );
				}
			}
		}
	}

	if (minNum[M][N] >= INF) {
		puts("Impossible");
	}
	else {
		printf("%d\n", minNum[M][N]);
	}
}

int main() {
	init();
	solve();

	return 0;
}