acm.xmu.edu.cn上的1303題。
此題為廈門(mén)大學(xué)信息科學(xué)與技術(shù)學(xué)院暑期ACM培訓(xùn)的內(nèi)部測(cè)試題。
直接看題，明顯為一維區(qū)間的動(dòng)態(tài)規(guī)劃。
1 #include<stdio.h>
2 char array[110];
3 int zero,one;
4 int i;
5 int dp(int n)
6 {
7 if(array[0] == '0')
8 {
9 zero = 0;
10 one = 1;
11 }
12 else
13 {
14 zero = 1;
15 one = 0;
16 }
17 for(i = 1;i < n;++i)
18 {
19 if(array[i] == '0')
20 {
21 if(array[i] != array[i - 1])
22 ++one;
23 }
24 else
25 {
26 if(array[i] != array[i - 1])
27 ++ zero;
28 }
29 }
30 return zero < one?zero:one;
31 }
32
33 int main()
34 {
35 int t,n;
36 scanf("%d",&t);
37 while(t-- != 0)
38 {
39 scanf("%d",&n);
40 scanf("%s",array);
41 printf("%d\n",dp(n));
42 }
43 return 0;
44 }
posted on 2012-04-06 10:35
崔佳星 閱讀(144)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
xoj