[文章目录]
Description
农夫约翰有N(1≤N≤5000)只牛站成一排，有一些很乖的牛朝前站着．但是有些不乖的牛却朝后站着．农夫约翰需要让所有的牛都朝前站着．幸运的是约翰最近买了一个自动转身机．这个神奇的机器能使K(1≤K≤N)只连续的牛转身． 因为约翰从来都不改变K的价值，请帮助他求出K，使旋转次数M达到最小．同时要求出对应的M.
一开始理解错了，每次选k个的时候只能选连续k个，不能由于边界的借口来选少于k个。。。
那么发现覆盖到第一个牛的区间只有一个，那么这个区间选的状态是固定的，其余同理。枚举k求m。当前区间是否旋转取决于前k-1个位置开头的区间旋转状态以及当前位置的状态决定，维护一个长度为k的区间旋转次数状态就好了。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,ans=0x3f3f3f3f,fna;
bool f[5100];
bool v[5100];
int calc(int x)
{
memset(v,0,sizeof v);
int re=0; bool sum=0;
for(int i=1;i<=n;++i)
{
if(i-x>0) sum^=v[i-x];
if(f[i]^sum)
{
if(n-i+1<x) return 0x3f3f3f3f;
v[i]=1,re++,sum^=1;
}
}
return re;
}
int main()
{
scanf("%d",&n); char sw[10];
for(int i=1;i<=n;++i)
{
scanf("%s",sw);
if(sw[0]=='B') f[i]=1;
else f[i]=0;
}
for(int k=1;k<=n;++k)
{
int tmp=calc(k);
if(tmp<ans) ans=tmp,fna=k;
}
for(int i=1;i<=n;++i)
if(f[i])
{
printf("%d %d\n",fna,ans);
return 0;
}
puts("0 0");
}