题意

有n头奶牛排成一队，有的脸朝前有的脸朝后，F代表前，B代表后。现在有一种操作可以让连续K头奶牛同时反转，问至少要反转多少次，此时K至少为多少。先输出K，再输出最小反转次数。

Input

7
B
B
F
B
F
B
B

Output

3 3

题解

显然我们需要从1到n挨个尝试K的可能取值，并从中选取最优，主要问题在于怎么算K一定时的最小反转次数呢？自然想到遍历区间。从[1,k]区间遍历到[n-k+1,n]，对于每一个区间，如果区间的第一个是反的，那么我们就把整个区间反转。

考虑差分，即每次只修改$i…i+k−1$,然后通过前缀和求解每一位是否反转。反转奇数次使方向相反，偶数次使方向不变。最后的总复杂度是$O(n^2)$

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
typedef pair<int,int> PII;
typedef long long LL;
const int INF=0x3f3f3f3f;

const int N=5010;
int a[N];
int b[N];//差分数组
int n;

int solve(int k)
{
    memset(b,0,sizeof b);
    int cnt=0;

    for(int i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        if(i+k-1<=n)
        {
            if((a[i]+b[i])%2 != 0)
            {
                b[i]++;
                b[i+k]--;
                cnt++;
            }
        }
        else
        {
            if((a[i]+b[i])%2 != 0)
                return INF;
        }
    }
    return cnt;
}


int main()
{
    scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        a[i]=(c=='B'?1:0);
    }

    int ansk=1,ansm=n;
    for(int i=1;i<=n;i++)
    {
        int res=solve(i);
        if(res<ansm)
        {
            ansk=i;
            ansm=res;
        }
    }

    cout<<ansk<<' '<<ansm<<endl;
   // system("pause");
}