首页 > 代码库 > poj3276 Face The Right Way

poj3276 Face The Right Way

Face The Right Way

 POJ - 3276 

题目大意:

n头牛排成一列,每头牛向前或向后,为了让所有牛都面向前方,设定一个k值,每操作一次恰好使k头连续的牛转向,求最少的操作次数m和对应的最小的k

(B向后;F向前;输出为k m)

Sample Input

7BBFBFBB

Sample Output

3 3
/*    枚举k值,对于枚举到的每个k值,求其m    对于一个长为k的区间的反转,不需要挨个模拟,设一个数组f[]    f[i]记录第i个位置上的牛被反转了多少次     在考虑第i头牛时,如果f[i-k+2]~f[i-1]所有的和为奇数的话,则这头牛与起始方向是相反的 */#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 5010int n,a[maxn],f[maxn],m,k,M=0x7fffffff;char s[10];int calc(int K){    memset(f,0,sizeof(f));    int res=0;    int sum=0;    for(int i=1;i+K-1<=n;i++){        if((a[i]+sum)%2!=0){//这个位置被翻转了             res++;            f[i]=1;        }        sum+=f[i];        if(i-K>=0)sum-=f[i-K+1];//保证sum涵盖的是i-K+1~i-1     }    for(int i=n-K+2;i<=n;i++){        if((a[i]+sum)%2!=0)//还背对着             return -1;        if(i-K+1>=0)            sum-=f[i-K+1];    }    return res;}int main(){    //freopen("Cola.txt","r",stdin);    scanf("%d",&n);    for(int i=1;i<=n;i++){        scanf("%s",s);        if(s[0]==B)a[i]=1;        else if(s[0]==F)a[i]=0;    }    for(int i=1;i<=n;i++){        m=calc(i);        if(m>=0&&M>m){            M=m;            k=i;        }    }    printf("%d %d\n",k,M);}

 

poj3276 Face The Right Way