题目链接：http://codeforces.com/problemset/problem/698/A
很久很久没做咯~~~~
dp 是个很神奇的东西。。。。
1 #include2 #include 3 #include 4 #include 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/rest12 // 2:sport/rest 3:sport/contest/rest13 14 int main()15 {16 int n, a;17 #ifndef ONLINE_JUDGE18 freopen("in.txt", "r", stdin);19 #endif // ONLINE_JUDGE20 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) { // contest45 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) { // sport49 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) { // rest54 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/c60 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 }