POJ3276
题意：
N 头牛排成一列，每头牛或向前或向后。每次可以反转连续的 K 头牛，求出让所有的牛都能面向前方所需要的最少操作次数 M 和对应的最小的 K。
解法：
首先加入顺序的枚举每个以向后的牛开始的区间，让其反转，之后检查可行性，复杂度为 $O(n^3)$，即顺序遍历、反转、寻找第一个面向正面的奶牛，不可取。
所以这种问题的关键就是怎样优化区间反转的那一部分。
设：$f[i] = $区间$[i,i+K-1]$进行了反转的话则为$1$，否则为$0$.
这样在考虑第 i 头牛的时候，如果 $\sum_{j=i-K+1}^{i-1}f[j]$为奇数的话，则这头牛的方向与起始方向是相反的，否则方向不变
又因为：$\sum_{j=(i+1)-K+1}^{i}f[j]=\sum_{j=i-K+1}^{i-1}f[j]+f[i]-f[i-K+1]$
这样每个区间的牛的反转情况就可以在$O(1)$的时间内算出来，可解。
1 int N;
2 int dir[MAXN]; // 牛的方向（0：F，1：B）
3 int f[MAXN]; //区间（i，i-K+1）是否进行反转
4
5 //固定K，求对应的最小操作回数
6 //无解返回-1
7 int calc(int K) {
8 MEM(f, 0);
9 int res = 0;
10 int sum = 0; // f的和
11 for (int i = 0; i + K <= N; i++) {
12 if ((dir[i] + sum) % 2 != 0) {
13 // 前端的牛朝后方
14 res++;
15 f[i] = 1;
16 }
17 sum += f[i];
18 if (i - K + 1 >= 0) sum -= f[i - K + 1];
19 }
20 //检查剩下的牛是否有朝后方的情况
21 for (int i = N - K + 1; i < N; i++) {
22 if ((dir[i] + sum) % 2 != 0) return -1; //无解
23 if (i - K + 1 >= 0) sum -= f[i - K + 1];
24 }
25 return res;
26 }
27
28 void solve() {
29 int K = 1, M = N;
30 for (int k = 1; k <= N; k++) {
31 int m = calc(k);
32 if (m > 0 && M > m) {
33 M = m;
34 K = k;
35 }
36 }
37 printf("%d %d\n", K, M);
38 }
39
40 int main() {
41 #ifndef ONLINE_JUDGE
42 freopen("input.txt", "r", stdin);
43 #endif
44 scanf("%d", &N);
45 REP(i, 0, N - 1) {
46 char c[2];
47 scanf("%s", c);
48 dir[i] = (c[0] == 'F') ? 0 : 1;
49 }
50 solve();
51 return 0;
52 }