POJ 2978 - Colored stones

http://poj.org/problem?id=2978

概要

\(m\) 個の石が一直線に並べられており，それぞれ \(x_i\) の色で塗られている． 色は全部で \(k\) 種類ある．

任意の同じ色の2つの石について，その2つの石の間にそれとは異なる色の石が無いようにしたい． このとき，取り除く必要がある石の最小値を答える．

制約

解法

$$\mathit{dp}(i, j, s) = \mbox{\(i\) 番目の石までで，最後の色が \(j\) で今までに使った色の状態が \(s\) のときの最小値}$$

という DP 表を埋めて \(\mbox{min}_{1 \le j \le k, 0 \le s < 2^k}\{\mathit{dp}(m, j, s)\}\) が答え．

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int M, K;
 8   while (cin >> M >> K && M != 0) {
 9     static int dp[100][5][1<<5];
10     static const int INF = 10000000;
11     for (int i = 0; i < M; i++) {
12       for (int j = 0; j < K; j++) {
13         fill_n(dp[i][j], 1<<K, INF);
14       }
15     }
16 
17     static int a[100];
18     for (int i = 0; i < M; i++) {
19       cin >> a[i];
20       --a[i];
21     }
22 
23     for (int j = 0; j < K; j++) {
24       if (j == a[0]) {
25         dp[0][j][1<<j] = 0;
26       } else {
27         dp[0][j][1<<j] = 1;
28       }
29     }
30     for (int i = 0; i < M-1; i++) {
31       for (int j = 0; j < K; j++) {
32         for (int k = 0; k < (1<<K); k++) {
33           if (!(k & (1<<j))) {
34             continue;
35           }
36           dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + (a[i+1] != j));
37           if (!(k & (1<<a[i+1]))) {
38             const int s = k | (1<<a[i+1]);
39             dp[i+1][a[i+1]][s] = min(dp[i+1][a[i+1]][s], dp[i][j][k]);
40           }
41         }
42       }
43     }
44 
45     int ans = INF;
46     for (int j = 0; j < K; j++) {
47       for (int k = 0; k < (1<<K); k++) {
48         ans = min(ans, dp[M-1][j][k]);
49       }
50     }
51     cout << ans << endl;
52   }
53   return 0;
54 }
poj/2978.cc