http://acm.pku.edu.cn/JudgeOnline/problem?id=3670
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5 const int N=30005;
6 int dp1[N];
7 int dp2[N];
8 int dp3[N];
9 int d1[N];
10 int d2[N];
11 int main()
12 {
13 int n;
14 while(cin>>n){
15 int num;
16 memset(dp1,0,sizeof(dp1));
17 memset(dp2,0,sizeof(dp2));
18 memset(dp3,0,sizeof(dp3));
19 for(int i=0;i<n;i++){
20 cin>>d1[i];
21 d2[n-i-1]=d1[i];
22 }
23 switch(d1[0]){
24 case 1:
25 dp1[0]=0,dp2[0]=1,dp3[0]=1;
26 break;
27 case 2:
28 dp1[0]=1,dp2[0]=0,dp3[0]=1;
29 break;
30 case 3:
31 dp1[0]=1,dp2[0]=1,dp3[0]=0;
32 break;
33 }
34
35 for(int i=1;i<n;i++){
36 switch(d1[i]){
37 case 1:
38 dp1[i]=dp1[i-1];
39 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
40 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
41 break;
42 case 2:
43 dp1[i]=dp1[i-1]+1;
44 dp2[i]=min(dp1[i-1],dp2[i-1]);
45 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
46 break;
47 case 3:
48 dp1[i]=dp1[i-1]+1;
49 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
50 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]));
51 break;
52 }
53 }
54 int ans=0x7fffffff;
55 if(ans>dp1[n-1])ans=dp1[n-1];
56 if(ans>dp2[n-1])ans=dp2[n-1];
57 if(ans>dp3[n-1])ans=dp3[n-1];
58
59 switch(d2[0]){
60 case 1:
61 dp1[0]=0,dp2[0]=1,dp3[0]=1;
62 break;
63 case 2:
64 dp1[0]=1,dp2[0]=0,dp3[0]=1;
65 break;
66 case 3:
67 dp1[0]=1,dp2[0]=1,dp3[0]=0;
68 break;
69 }
70
71 for(int i=1;i<n;i++){
72 switch(d2[i]){
73 case 1:
74 dp1[i]=dp1[i-1];
75 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
76 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
77 break;
78 case 2:
79 dp1[i]=dp1[i-1]+1;
80 dp2[i]=min(dp1[i-1],dp2[i-1]);
81 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
82 break;
83 case 3:
84 dp1[i]=dp1[i-1]+1;
85 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
86 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]));
87 break;
88 }
89 }
90
91 if(ans>dp1[n-1])ans=dp1[n-1];
92 if(ans>dp2[n-1])ans=dp2[n-1];
93 if(ans>dp3[n-1])ans=dp3[n-1];
94
95 cout<<ans<<endl;
96 }
97 return 0;
98 }
99
posted on 2008-07-25 15:27
小果子 閱讀(216)
評論(0) 編輯 收藏 引用