https://www.luogu.org/problem/P2882
题意
你有n头牛,每头牛有个朝向,你每次可以选择连续k头牛翻转,求k为多少时可以用最少的步骤将所有牛朝向变为正向
n≤5000
分析
我们知道, 对于一个序列,我们如果选择每次翻k头牛,最优的翻转策略就是,每次找到第一头反向的牛,然后将它和后面的牛,一共k头都翻转,然后再往后找到第一个反向的牛,再...(因为每头牛都要翻正,如果先找到的是第一头反向的牛的前面或后面的牛翻转,那么就会造成额外的操作)
于是我们的做法是暴力枚举k,然后check出最佳的m,然而O(n^3)(check是O(nk)的),显然过不去,需要优化。
我们可以利用1为正向,0为反向,然后一个差分,用一个延迟标记tag,每次判断的时候用原数加上这个tag, 结果如果是奇数,就说明是正向的, 就不操作;如果是偶数,就是反向的,这时候操作数m++, 然后在翻转的右边界的右一个打上一个差分标记cf[i+k]=-1,而且我们cf的初值为0,这样就可以简单地更新tag啦。
注意不能再翻转的时候
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<iostream>
using namespace std;
#define MAX 5000+9
int n, m;
int a[MAX];
int cf[MAX],is;
void check(int k) {
int tag = 0;
for(int i = 1; i <= n; i++) {
tag += cf[i];
if((a[i]+tag) % 2 == 0) {
if(i+k-1 > n) {
m = MAX;
return ;
}
tag++;
cf[i+k]--;
m++;
}
}
}
int main() {
scanf("%d",&n);
char c;
for(int i = 1; i <= n; i++) {
cin>>c;
if(c == 'F') a[i] = 1;//正
else a[i] = 0, is = 1;
}
if(is == 0) {
printf("1 0");
return 0;
}
int ansm = MAX, ansk;
for(int k = 1; k <= n; k++) {
memset(cf, 0, sizeof(cf));
check(k);
if(ansm > m) {
ansm = m;
ansk = k;
}
m = 0;
}
printf("%d %d",ansk, ansm);
}