[USACO07MAR] Face The Right Way G

题目描述

DESCRIPTION

Farmer John has arranged his $N$ ($1 \leq N \leq 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 \leq K \leq N$) 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 FORMAT

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 FORMAT

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)$

题目大意

$N$ 头牛排成一列 $1 \le N \le 5000$。每头牛或者向前或者向后。为了让所有牛都面向前方，农夫每次可以将 $K$ 头连续的牛转向 $1 \le K \le N$，求使操作次数最小的相应 $K$ 和最小的操作次数 $M$。$F$ 为朝前，$B$ 为朝后。

请在一行输出两个数字 $K$ 和 $M$，用空格分开。

题解

因为一个点翻转两次和没有翻转的效果相同，所以对于每个点而言，只有 不翻转 和 翻转一次 两种可能性，将原序列的 B 和 F 分别抽象为 0 和 1 ，构成01序列 $A$ ，对第$i$的翻转操作就相当于 $A_i \oplus 1$ .

考虑贪心，顺序遍历每一位，如果当前位为 0 ( B )，则将以该位为起点，长度为$K$的子串全部翻转，判断是否能够将$A$的每一位置为 1 ( F ).

同时我们可以发现，使操作次数最小的相应 $K$ 和最小的操作次数 $M$ 并不具有单调性，只能通过枚举取得最优值，这样的时间复杂度是 $O(n^3)$ 并不能通过此题，必须再优化一维.

注意到贪心的过程中，我们对序列 $A$ 进行的是 区间修改单点查询 的操作，同时异或运算支持前缀和的操作，这里可以使用差分进行优化，这样时间复杂度就能降到 $O(n^2)$ 了.

代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
char ch;

bool a[N], d[N];

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> ch;
        a[i] = ch == 'F';
    }
    int k, m = INT_MAX;
    for (int l = 1; l <= n; l++)
    {
        memset(d, 0, sizeof(d));
        bool sum = 0, flag = true;
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            sum ^= d[i];
            if (a[i] ^ sum)
                continue;
            if (i + l - 1 > n)
            {
                flag = false;
                break;
            }
            sum ^= 1;
            d[i + l] ^= 1;
            cnt++;
        }
        if (flag)
        {
            if (m > cnt)
            {
                m = cnt;
                k = l;
            }
        }
    }
    cout << k << " " << m << endl;
    return 0;
}