POJ3276 Face The Right Way (尺取法)

题目描述

Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facing backward, though, and he needs them all to face forward to make his life perfect.

Fortunately, FJ recently bought an automatic cow turning machine. Since he purchased the discount model, it must be irrevocably preset to turn K (1 ≤ KN)cows at once, and it can only turn cows that are all standing next to each other in line. Each time the machine is used, it reverses the facing direction of a contiguous group of K cows in the line (one cannot use it on fewer than K cows, e.g., at the either end of the line of cows). Each cow remains in the same *location* as before, but ends up facing the *opposite direction*. A cow that starts out facing forward will be turned backward by the machine and vice-versa.

Because FJ must pick a single, never-changing value of K, please help him determine the minimum value of K that minimizes the number of operations required by the machine to make all the cows face forward. Also determine M, the minimum number of machine operations required to get all the cows facing forward using that value of K.

Input

Line 1: A single integer: N
Lines 2..
N+1: Line
i+1 contains a single character,
F or
B, indicating whether cow
i is facing forward or backward.

Output

Line 1: Two space-separated integers:
K and
M

Sample Input

7
B
B
F
B
F
B
B

Sample Output

3 3

Hint

For K = 3, the machine must be operated three times: turn cows (1,2,3), (3,4,5), and finally (5,6,7)

思路

  这道题需要用到‘尺取法’,根据我在网上找的题解来看,这道题所用的尺取法就是依次选定我们更改的长度k,在我们需要操作的序列上依次进行区间修改。这就有点类似于贪心的思路。我们在反转时需要注意以下两点:

1、交换区间反转的顺序对结果是没有影响的。

2、对同一个区间进行两次以上的反转是多余的。

我们选定k之后从1到i-k+1依次走一遍,若这个数此时(在原来基础上加上修改次数)朝后,则将以这个数为起点的长度为k的区间进行修改,在修改完之后的操作由于起点都在该点之后,将不会再对该点的状态造成影响。

由于我们要知道该点已经修改几回,则需要维护所有前面已经修改过的且包含该点的次数。我们用一个sum来表示从i-k+1到i-1的修改次数,用ans来存储总的修改次数,即j从i-k+1到i-1的区间和,在走完每一个k值之后,由于sum(i-k+2~i)=sum(i-k+1~i-1)-j[i-k+1]+j[i];我们在跑完一次i要进入下一区间时,我们直接进行

sum+=f[i];

if(i-k+1>=1) sum-=f[i-k+1];

即可维护下一状态的sum值。

最后判断n-k+2到n是不是都朝前看,如果是则记录答案。

最后注意题目要求求操作次数最小值,k从1到n都取一遍,取ans最小值即可。

最后上代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 const int N=5e3+10;
 5 int n,f[N];
 6 char c[N];
 7 int cow(int k){
 8     memset(f,0,sizeof(f));
 9     int ans=0,sum=0;
10     for(int i=1;i<=n-k+1;++i){
11         if(sum%2==0&&c[i]==‘B‘)
12             f[i]=1,ans++;
13         else if(sum%2==1&&c[i]==‘F‘)
14             f[i]=1,ans++;
15         sum+=f[i];
16         if(i-k+1>=1) sum-=f[i-k+1];
17     }
18     for(int i=n-k+2;i<=n;++i){
19         if(sum%2==0&&c[i]==‘B‘) return -1;
20         else if(sum%2==1&&c[i]==‘F‘) return -1;
21         sum+=f[i];
22         if(i-k+1>=1) sum-=f[i-k+1];
23     }
24     return ans;
25 }
26 int main(){
27     scanf("%d",&n);
28     int m=2147483617,k;
29     for(int i=1;i<=n;++i) scanf(" %c",&c[i]);
30     for(int i=1;i<=n;++i){
31         int cnt=cow(i);
32         if(cnt>=0&&cnt<m)
33             k=i,m=cnt;
34     }
35     printf("%d %d\n",k,m);
36     return 0;
37 }

本文多处借鉴这篇博客https://blog.csdn.net/qq_40889820/article/details/82785549。

原文地址:https://www.cnblogs.com/li-jia-hao/p/12639955.html

时间: 04-05

POJ3276 Face The Right Way (尺取法)的相关文章

POJ3276 Face The Right Way 【尺取法】

Face The Right Way Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 2721   Accepted: 1246 Description Farmer John has arranged his N (1 ≤ N ≤ 5,000) cows in a row and many of them are facing forward, like good cows. Some of them are facin

luogu 1712 区间(线段树+尺取法)

题意:给出n个区间,求选择一些区间,使得一个点被覆盖的次数超过m次,最小的花费.花费指的是选择的区间中最大长度减去最小长度. 坐标值这么大,n比较小,显然需要离散化,需要一个技巧,把区间转化为半开半闭区间,然后线段树的每一个节点表示一个半开半闭区间. 接着我们注意到需要求最小的花费,且这个花费只与选择的区间集合中的最大长度和最小长度有关. 这意味着如果最大长度和最小长度一定,我们显然是需要把中间长度的区间尽量的选择进去使答案不会变的更劣. 不妨把区间按长度排序,枚举每个最小长度区间,然后最大区间

poj 3320 Jessica&#39;s Reading Problem(尺取法+map/hash)

题目:http://poj.org/problem?id=3320 题意:给定N个元素的数组,找出最短的一段区间使得区间里面的元素种类等于整个数组的元素种类. 分析:暴力枚举区间的起点x,然后找到最小的y,使得区间[x,y]满足条件,x向有移位后变成x',现在的y'肯定不至于在y的左边.存状态的话map和hash都可以. map代码: #include <iostream> #include <set> #include <map> #include <cstdi

hihocoder-1483区间价值 (二分+尺取法)

题目链接: 区间价值 给定n个数A1...An,小Ho想了解AL..AR中有多少对元素值相同.小Ho把这个数目定义为区间[L,R]的价值,用v[L,R]表示. 例如1 1 1 2 2这五个数所组成的区间的价值为4. 现在小Ho想知道在所有的的v[L,R](1 <= L <= R <= n)中,第k小的值是多少. Input 第一行一个数T(T<=10),表示数据组数. 对于每一组数据: 第一行两个数n,k(1<=n<=200,000,1<=k<=n*(n+1

【转】毛虫算法&mdash;&mdash;尺取法

转自http://www.myexception.cn/program/1839999.html 妹子满分~~~~ 毛毛虫算法--尺取法 有这么一类问题,需要在给的一组数据中找到不大于某一个上限的"最优连续子序列" 于是就有了这样一种方法,找这个子序列的过程很像毛毛虫爬行方式,我管它叫毛毛虫算法,比较流行的叫法是"尺取法". 喏,就像图里的妹纸一样~ 还是举个栗子: Poj3061 给长度为n的数组和一个整数m,求总和不小于m的连续子序列的最小长度 输入 n = 1

51nod1127(尺取法)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1127 题意:中文题诶- 思路:尺取法 维护一个队列,若当前队首的元素在后面出现了,那么我们就将其删除,若当前队列里含有26个字母,我们就记录其size. 取所有size里面的最小值就是我们要的答案... 代码: 1 #include <iostream> 2 #include <stdio.h> 3 #include <string>

BestCoder Round #86 二,三题题解(尺取法)

第一题太水,跳过了. NanoApe Loves Sequence题目描述:退役狗 NanoApe 滚回去学文化课啦! 在数学课上,NanoApe 心痒痒又玩起了数列.他在纸上随便写了一个长度为 nnn 的数列,他又根据心情随便删了一个数,这样他得到了一个新的数列,然后他计算出了所有相邻两数的差的绝对值的最大值. 他当然知道这个最大值会随着他删了的数改变而改变,所以他想知道假如全部数被删除的概率是相等的话,差的绝对值的最大值的期望是多少. 输入描述 第一行为一个正整数 T,表示数据组数. 每组数

POJ 3320 尺取法,Hash,map标记

1.POJ 3320 2.链接:http://poj.org/problem?id=3320 3.总结:尺取法,Hash,map标记 看书复习,p页书,一页有一个知识点,连续看求最少多少页看完所有知识点 必须说,STL够屌.. #include<iostream> #include<cstring> #include<cmath> #include<queue> #include<algorithm> #include<cstdio>

HDU 5672 String 尺取法追赶法

String Problem Description There is a string S.S only contain lower case English character.(10≤length(S)≤1,000,000)How many substrings there are that contain at least k(1≤k≤26) distinct characters? Input There are multiple test cases. The first line