N头牛站成一排，每头牛要么向前要么向后（F表示向前，B表示向后），为了让所有的牛都面向前方，约翰买了一台自动旋转的机器，每次旋转设定一个固定的k值，机器操作一次就旋转连续的k头牛，求出为了让所有牛都面向前方的的最少操作次数m和对应的k值。
用f[i]表示第i头牛旋转与否，f[i]=0表示不旋转，f[i]=1表示旋转，用a[i]表示第i头牛的方向，a[i]=0表示向前，a[i]=1表示向后，可以知道f[i-k+1]+f[i-k+2]+…+f[i-2]+f[i-1]为奇数表明第i头牛转到了相反的方向，为偶数则表示旋转之后方向没有改变。f[i-k+1]+f[i-k+2]+…+f[i-2]+f[i-1]+a[i]为奇数表名第i头牛需要旋转，否则不需要，也就是f[i]=f[i-k+1]+f[i-k+2]+…+f[i-2]+f[i-1]+a[i]。所以先枚举k的值，再检查是否能够找到合法方案。不过还有一些小细节需要注意。
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int MAXN=5010; int a[MAXN]; int f[MAXN]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { char s[2]; scanf("%s",s); if(s[0]=='F')a[i]=0; else a[i]=1; } int cnt = 1; int ans = n; for(int k=1; k<=n; k++) { int res = 0; int sum = 0;//sum表示f数组的和 memset(f,0,sizeof f); //计算区间[i,i+k-1] for(int i=1; i+k<=n+1; i++) { int flag=0; if((sum+a[i])%2!=0) { f[i]=1; res++; } sum+=f[i]; if(i+1-k>=1) { sum-=f[i+1-k]; } } int flag=0; //检查后面的牛是否有朝后的情况 for(int i=n-k+1+1; i<=n; i++) { if((sum+a[i])%2==1) { //无解 flag=1; break; } if(i-k+1>=1)sum-=f[i+1-k]; } if(res<ans&&flag==0) { ans=res; cnt=k; } } cout<<cnt<<" "<<ans<<endl; return 0; }