题目链接:http://codeforces.com/problemset/problem/327/A
题意是输入一个只有0和1的序列,要求找出一个合理的区间,在这个区间里面把0变成1,1变成0,使得该区间和该区间外的1的个数达到最大。
一开始的的思路是:找最大的0区间(序列中头尾第一次遇到0所夹的区间),然后在这个区间里暴搜(保证该区间内细分到的小区间都搜索过),统计0的个数(由于0会变成1,1自然会变成0,所以没有必要统计1的个数)。但是问题是这样做的话,该区间1的个数和0的个数的多少是不确定的:0<1 , 1 >0 还是 0 == 1。有很多不确定的因素,因此不能保证所找到的0区间是最优的。正确的做法是:找出的最优区间应该满足0个数最多,1个数最少。这样才能够保证整个序列中1的总数是最多的。
1 #include <iostream> 2 #include <stdlib.h> 3 #include <stdio.h> 4 using namespace std; 5 6 const int maxn = 100+10; 7 8 int main() 9 { 10 int n, a[maxn], i, j, m, count1, count0, max, t0, t1, t; 11 while (cin >> n) 12 { 13 for (t = i = 0; i < n; i++) 14 { 15 scanf("%d", &a[i]); 16 if (a[i]) 17 t++; // 统计整个序列中1的个数 18 19 } 20 max = -10; 21 for (i = 0; i < n; i++) 22 { 23 for (j = i; j < n; j++) 24 { 25 count1 = count0 = 0; 26 for (m = i; m <= j; m++) // 暴搜,统计每个区间的0、1数目 27 { 28 if (a[m]) 29 count1++; 30 else 31 count0++; 32 } 33 if (max < count0 - count1) // max保存的是当前0、1数目最大的差(0最多,1最少) 34 { 35 max = count0 - count1; 36 // t0 = count0; 37 // t1 = count1; 38 } 39 } 40 } 41 // cout << "t0 = " << t0 << endl; 42 // cout << "t1 = " << t1 << endl; 43 printf("%d\n", t + max); 44 } 45 return 0; 46 }