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; }