[原题]N头牛排成了一列。每头牛头向前或向后。为了让所有的牛都面向前方,农夫约翰买了一台自动转向的机器。这个机器在购买时就必须设定一个数值K,机器每操作一次恰好使K头连续的牛转向。求让所有牛都能面向前方需要的最少操作次数M和对应的最小的K.
如果按照枚举做肯定会TLE,首先排除。
交换区间翻转的顺序对结果是没有影响的。而且没有必要对同一个区间进行两次以上的翻转。因此问题转化成了求需要被翻转区间的集合。
f[i]:区间[i, i K-1] 进行可反转的话为1, 否则为0。
因此首先从最左侧牛开始考虑,如果该牛朝向前方,则不需要翻转这个区间;反之如果该牛朝后,则必须要处理这个区间,并且再次之后不需要考虑此最左的区间,区间范围-1。循环往返,即可求出最少翻转次数。
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.icode9.com/content-4-270851.html
联系客服