开关问题

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 }