首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。