题目链接：http://poj.org/problem?id=3276
题意：给定n头牛的朝向，每次反转k头牛，使得所有牛的朝向都为F，输出反转次数最小时的k和m（一定有解）
思路：同一个区间反转 两次及以上是多余的，区间反转的顺序对结果没影响
#include <cstdio>
#include <iostream>
#include <string.h>using namespace std;
#define INF 0x3f3f3f3fint dir[5050]={0};
int fz[5050]={0};
int n;int face(int k)
{int sum=0;int ans=0;memset(fz,0,sizeof(fz)); //注意每次调用face函数都要重置fzfor(int i=0;i<n-k+1;i++){if((dir[i]+sum)%2!=0){fz[i]=1;ans++;}sum+=fz[i];if(i-k+1>=0){sum-=fz[i-k+1];}}for(int i=n-k+1;i<n;i++){if((dir[i]+sum)%2!=0)return -1;if(i-k+1>=0){sum-=fz[i-k+1];}}return ans;
}void solve()
{int m=INF;int ans=0;int k;for( k=1;k<=n;k++){if(face(k)!=-1 && face(k)<m){m=face(k);ans=k;}}printf("%d %d\n",ans,m);
}int main()
{cin>>n;for(int i=0;i<n;i++){char tmp;getchar();scanf("%c",&tmp);if(tmp=='B')dir[i]=1;elsedir[i]=0;}solve();return 0;
}