【开关问题】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-k if((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++){//列举出所有可能的k int tres=solve(k); if( tres >=0 && tres<minres){ //这里判断一下大于0，说明可行 minres=tres; mink=k; } } printf("%d %d\n",mink,minres); } return 0; }