POJ 3276 Face The Right Way （常用技巧-尺取法）

POJ 3276 Face The Right Way （常用技巧-尺取法）

【题目链接】：​​click here~~​​

【题目大意】：N头牛排成一列1<=N<=5000。每头牛或者向前或者向后。为了让所有牛都 面向前方，农夫每次可以将K头连续的牛转向1<=K<=N，求操作的最少 次数M和对应的最小K。

【思路】：由于交换区间翻转顺序对结果没影响，所以从左往右对于需要  翻转的牛进行反转，同时记录对该区间其他牛的影响即cal中的sum， 对于最后部分无法翻转的区间检查是否有反向牛，若有则方案失败。此题思想值得细细思考，常常有一种无限状态，化为有限状态。

代码：

/***************POJ 3276 (尺取法)*Face The Right Way***************/#include #include #include using namespace std;const int N=5005;int t,n,m;int f[N]; //翻转状态，1翻转，0不翻转int dir[N]; // 输入状态 F<>0 B<>1char op[2];int calc(int k){ //枚举k ,翻转顺序从左到右 memset(f,0,sizeof(f)); int i,res=0; // 连续翻转的次数 int sum=0; for(i=0; i+k<=n; ++i){ if((dir[i]+sum)&1){ //翻转奇数次改变状态，偶数次不改变 res++; f[i]=1; } sum+=f[i]; //尺取法 if(i-k+1>=0) sum-=f[i-k+1]; } for(; i=0) sum-=f[i-k+1]; } return res;}void solve(){ int K=1,M=n; for(int i=1; i<=n; ++i){ int m=calc(i); if(m>0&&m

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。