题解 P2882 【[USACO07MAR]面对正确的方式Face The Right Way】

zhm411821 · 2016-10-28 19:34:38 · 题解

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a[10100],ans=100000000,b[10100],m;
char x;
void work(int k){
    int s=0,sum=0;
    memset(a,0,sizeof(a));
    for(int i=1;i<=n-k+1;i++){//如果变换两次，则等于没有变换
        if(sum%2==1 && b[i]){//判断第i位是否需要转换
            a[i]=1;
            s++;
        }
        if(sum%2==0 && (!b[i])){
            a[i]=1;//如果变换，打下一个标记
            s++;
        }
        sum+=a[i];
        if(i-k+1>=0)//计算有几次变换影响到了下一位
            sum-=a[i-k+1];
    }
    for(int i=n-k+2;i<=n;i++){
        if((sum%2==1 && b[i]) || (sum%2==0 && (!b[i]))) 
            return;
        if(i-k+1>=0)
            sum-=a[i-k+1];
    }
    if(ans>s){
        ans=s;
        m=k;
    }
    return;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){//将方向存为数字
        cin>>x;
        if(x=='F')
            b[i]=1;
        else
            b[i]=0;
    }
    for(int i=1;i<=n;i++)//枚举k，判断可行性
        work(i);
    cout<<m<<" "<<ans;
    return 0;
}