发现选定一个长度后,怎么翻转是固定的。
那我们直接选定一个长度去操作就行。
优化操作过程
类似于堆里打持久化标记一样的感觉。
[USACO07MAR]Face The Right Way G
// Problem: P2882 [USACO07MAR]Face The Right Way G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2882
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
#define N 5005
char a[N];
ll n;
ll ansm = 0x3f3f3f3f,ansk = 0;
ll tag[N];
inline ll check(int x){
ll t = 0,ans = 0;
std::memset(tag,0,sizeof(tag));
for(int i = 1;i <= n;++i){
t += tag[i];
if(t % 2 == 1 && a[i] == 'F')
if(i + x - 1<= n)
t++ , tag[i+x] -- ,ans ++ ;
else
return 0x3f3f3f3f;
if(t % 2 == 0 && a[i] == 'B')
if(i + x - 1<= n)
t++ , tag[i+x] -- ,ans ++ ;
else
return 0x3f3f3f3f;
}
return ans;
}
int main(){
scanf("%lld",&n);
for(int i = 1;i <= n;++i)
while(a[i] != 'B' && a[i] != 'F')
a[i] = getchar();
for(int i = 1;i <= n;++i){
ll z = check(i);
if(z < ansm){
ansm = z;
ansk = i;
}
}
std::cout<<ansk<<" "<<ansm<<std::endl;
}