POJ 3670 - Eating Together

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

概要

N 頭の牛が一直線に並んでおり，それぞれ3つのグループのうちのいずれかに属している．

何頭かの牛のグループを変更して，グループの番号が先頭から昇順あるいは降順になるようにしたい． そのときにグループを変更する必要がある最小の頭数を答える．

制約

• 1 <= N <= 3 * 10^4

解法

dp[i][j] = i 番目の牛のグループを j としたときの最適解

という DP を昇順・降順で2回やる．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int N;
 8   scanf("%d", &N);
 9   static const int MAXN = 30000;
10   static int a[MAXN];
11   for (int i = 0; i < N; i++) {
12     scanf("%d", &a[i]);
13     --a[i];
14   }
15 
16   static int dp1[MAXN][3], dp2[MAXN][3];
17   static const int INF = 10000000;
18   for (int i = 0; i < N; i++) {
19     fill_n(dp1[i], 3, INF);
20     fill_n(dp2[i], 3, INF);
21   }
22   for (int j = 0; j < 3; j++) {
23     dp1[0][j] = dp2[0][j] = j == a[0] ? 0 : 1;
24   }
25   for (int i = 1; i < N; i++) {
26     for (int j = 0; j < 3; j++) {
27       const int c = j == a[i] ? 0 : 1;
28       for (int k = 0; k <= j; k++) {
29         dp1[i][j] = min(dp1[i][j], dp1[i-1][k] + c);
30       }
31       for (int k = j; k < 3; k++) {
32         dp2[i][j] = min(dp2[i][j], dp2[i-1][k] + c);
33       }
34     }
35   }
36   int ans = INF;
37   for (int j = 0; j < 3; j++) {
38     ans = min(ans, dp1[N-1][j]);
39     ans = min(ans, dp2[N-1][j]);
40   }
41   printf("%d\n", ans);
42   return 0;
43 }