BZOJ1704: [Usaco2007 Mar]Face The Right Way 自动转身机

题解:

首先枚举$k$,那我们需要知道给定$k$,最少进行多少次操作.

显然应该从小到大进行扫描,考虑当前位置$i$,若颜色不对,则反转$[i,i+k-1]$.

然后再判定剩下的位置颜色对不对.

这个过程可以利用单调队列轻松实现,详情见代码.

代码:

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 5010
bool a[N];
int q[N],fr,ta;
int main(){
    int n;
    scanf("%d",&n);
    int i,j;
    char s[10];
    for(i=1;i<=n;++i){
        scanf("%s",s);
        a[i]=(s[0]=='F');
    }
    int ans=0x3f3f3f3f,temp,k;
    for(i=1;i<=n;++i){
        fr=ta=0;
        for(temp=0,j=1;j+i-1<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0){
                q[ta++]=j;
                ++temp;
            }
        }
        bool ok=1;
        for(j=n+2-i;j<=n;++j){
            while(fr!=ta&&q[fr]+i-1<j)
                ++fr;
            if((((ta-fr)&1)^a[j])==0)
                ok=0;
        }
        if(ok){
            if(temp<ans){
                ans=temp;
                k=i;
            }
        }
    }
    cout<<k<<" "<<ans<<endl;
    return 0;
}