acm.xmu.edu.cn上的1303題。
此題為廈門大學信息科學與技術(shù)學院暑期ACM培訓的內(nèi)部測試題。
直接看題，明顯為一維區(qū)間的動態(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
崔佳星 閱讀(146)
評論(0) 編輯 收藏 引用 所屬分類:
xoj