【开关问题】POJ 3276：Face The Right Way

本文主要是介绍【开关问题】POJ 3276：Face The Right Way，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目内容

POJ 3276 原题地址

二、题意解释

有n头牛，每头牛要么面朝前方或者面朝后方。现在可以连续驱使连续的k头牛反转。求使得所有的牛面朝前方的最小操作数和对应的k是多少？

三、代码及注释

#include<cstdio>
#include<string.h>
using namespace std;
const int Max_N=5001;
int dir[Max_N],f[Max_N],n;//dir记录其本身的方向，f记录他作为k长度的序列头时是否需要反转
int solve(int k){memset(f,0,sizeof(f));//每次都需要初始化一遍int sum=0,res=0;//sum统计的是k长度的区间中一共被反转的次数for(int i=0;i+k<=n;i++){//最后一次需要反转的坐标为n-kif((dir[i]+sum)%2!=0){//如果需要反转，那么反转一次f[i]=1;res++;}sum+=f[i];if(i-k+1>=0){//如果超过k长度序列外的反转次数就不需要考虑了，因为他不会影响再进入序列的反转sum-=f[i-k+1];}}for(int i=n-k+1;i<n;i++){//判断最后k-1长度的序列是否最终都是正向,应该从n-k+1坐标开始进行判断if((dir[i]+sum)%2!=0){return -1;}if(i-k+1>=0) sum-=f[i-k+1];}return res;
}
int main(){memset(dir,0,sizeof(dir));while(scanf("%d",&n)!=EOF){for(int i=0;i<n;i++){getchar();//识别换行符char ch;scanf("%c",&ch);if(ch=='B'){dir[i]=1;}}int mink=1,minres=n;for(int k=1;k<=n;k++){//列举出所有可能的kint tres=solve(k);if( tres >=0 && tres<minres){ //这里判断一下大于0，说明可行minres=tres;mink=k;}}printf("%d %d\n",mink,minres);}return 0;
}