acm.xmu.edu.cn上的1303题。
此题为厦门大学信息科学与技术学院暑期ACM培训的内部测试题。
直接看题，明显为一维区间的动态规划。
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
崔佳星 阅读(126)
评论(0) 编辑 收藏 引用 所属分类:
xoj