留只脚印（DP）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int max_day = 100 + 5;
 8 const int max_option = 3;
 9 
10 int dp[max_day][max_option];
11 // 0:rest  1:contest/rest
12 // 2:sport/rest  3:sport/contest/rest
13 
14 int main()
15 {
16     int n, a;
17     #ifndef ONLINE_JUDGE
18         freopen("in.txt", "r", stdin);
19     #endif // ONLINE_JUDGE
20     while (scanf("%d", &n) != EOF) {
21         memset(dp, 0, sizeof(dp));
22 
23         for (int i = 1; i <= n; i++) {
24             scanf("%d", &a);
25 
26             // 呢个野要时时刻刻更新，选择最优来更新，甘样就保证到 dp[i][1]和dp[i][2]都系最好噶啦
27             dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
28             if (a == 1 || a == 3) {
29                 dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + 1;   // +1 写出边，重要的事情说3遍！！！
30             }
31 
32             if (a == 2 || a == 3) {
33                 dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + 1;
34             }
35      //       printf("dp[%d][0]=%d, dp[%d][1]=%d, dp[%d][2]=%d\n", i, dp[i][0], i,dp[i][1], i,dp[i][2]);
36         }
37 
38 
39         printf("%d\n", n-max(dp[n][0], max(dp[n][1], dp[n][2])));
40 
41         /*  写错晒了。。。。脑退化 = =，好彩总算知道，dp[i][3] 系无鬼用的，后来知道左，改翻岩呢个细节，靠~ = =
42         for (int i = 1; i <= n; i++) {
43   //          dp[i][3] = max(dp[i-1][2], dp[i-1][1]) + 1;
44             if (a[i] == 1) {   // contest
45                 dp[i][0] = dp[i][1] = dp[i-1][2]+1;
46                 dp[i][2] = dp[i-1][2];
47             }
48             else if (a[i] == 2) {  // sport
49                 dp[i][0] = dp[i][2] = dp[i-1][1]+1;
50                 dp[i][1] = dp[i-1][1];
51      //           printf("dp[%d][2] = %d\n", i, dp[i][2]);
52             }
53             else if (a[i] == 0) {    // rest
54                 dp[i][0] = dp[i-1][0];
55                 dp[i][1] = dp[i-1][1];
56                 dp[i][2] = dp[i-1][2];
57        //         printf("dp[%d][0] = %d\n", i, dp[i][0]);
58             }
59             else {   // a[i] = 3  // s/r/c
60                 if (a[i-1] == 2) {
61                     dp[i][1] = dp[i-1][1] + 1;
62                     dp[i][2] = dp[i-1][2];
63                     dp[i][0] = dp[i-1][0];
64                 }
65                 else if (a[i-1] == 1) {
66                     dp[i][2] = dp[i-1][2] + 1;
67                 dp[i][0] = dp[i-1][0];
68                 dp[i][1] = dp[i-1][1];
69                 }
70 
71 
72                 /*
73                 if (a[i-1] == 0) {
74                     dp[i][3] = dp[i-1][0];
75                 }
76                 else if (a[i-1] == 1) {
77                     dp[i][3] = dp[i-1][2]+1;
78                 }
79                 else if (a[i-1] == 2) {
80                     dp[i][3] = dp[i-1][1]+1;
81                 }
82                 else {
83                     dp[i][3] = max(dp[i-1][2], dp[i-1][1]) + 1;
84                 }
85 
86   //
87 
88             }
89                printf("dp[%d][0] = %d\n", i, dp[i][0]);
90             printf("dp[%d][1] = %d\n", i, dp[i][1]);
91             printf("dp[%d][2] = %d\n", i, dp[i][2]);
92         }
93         printf("\ndp[%d][0]=%d, dp[%d][1]=%d, dp[%d][2]=%d\n", n, dp[n][0], n,dp[n][1], n,dp[n][2]);
94         */
95     }
96     return 0;
97 
98 }