【反转（开关问题）】Face The Right Way

?

• Step1 Problem:

[原题]N头牛排成了一列。每头牛头向前或向后。为了让所有的牛都面向前方，农夫约翰买了一台自动转向的机器。这个机器在购买时就必须设定一个数值K，机器每操作一次恰好使K头连续的牛转向。求让所有牛都能面向前方需要的最少操作次数M和对应的最小的K.

• Step2 Ideas:

?如果按照枚举做肯定会TLE，首先排除。
交换区间翻转的顺序对结果是没有影响的。而且没有必要对同一个区间进行两次以上的翻转。因此问题转化成了求需要被翻转区间的集合。
f[i]：区间[i, i K-1] 进行可反转的话为1， 否则为0。
因此首先从最左侧牛开始考虑，如果该牛朝向前方，则不需要翻转这个区间；反之如果该牛朝后，则必须要处理这个区间，并且再次之后不需要考虑此最左的区间，区间范围-1。循环往返，即可求出最少翻转次数。

• Step3 Code:

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<iomanip>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<map>
 8 #include<cmath>
 9 #include<set>
10 #define mem(a,x) memset(a,x,sizeof(a));
11 using namespace std;
12 typedef long long ll;
13 const int inf = 0x3f3f3f3f;
14 const ll INF = 0x3f3f3f3f3f3f3f3f;
15 const int maxn = 5e3 5;
16 int n, dir[maxn], f[maxn];
17 
18 int calc(int k)
19 {
20     mem(f, 0);
21     int res = 0;
22     int sum = 0;
23     for(int i = 0;i   k <= n; i  )
24     {
25         if((dir[i]   sum) % 2)
26         {
27             res  ;
28             f[i] = 1;
29         }
30         sum  = f[i];
31         if(i - k   1 >= 0) sum -= f[i - k   1];
32     }
33     for(int i = n - k   1; i < n; i  )
34     {
35         if((dir[i]   sum) % 2) return -1;
36         if(i - k   1 >= 0) sum -= f[i - k   1];
37     }
38     return res;
39 }
40 
41 int main()
42 {
43     cin >> n;
44     for(int i = 0; i < n; i  )
45     {
46         char c;
47         cin >> c;
48         dir[i] = (c == 'B');
49     }
50 //    for(int i = 0;i < n; i  ) cout << dir[i] << ' ';
51 //    puts("");
52     int k = 1, m = n;
53     for(int i = 1;i <= n; i  )
54     {
55         int x = calc(i);
56         if(x >= 0 && m > x)
57         {
58             k = i;
59             m = x;
60         }
61     }
62     cout << k << ' ' << m << endl;
63     return 0；
64 }

View Code

?

来源：https://www./content-4-270851.html