Poj 3276: Face The Right Way

poj3276.md

Poj 3276: Face The Right Way

題目

分析

書上例題…… 枚舉 + 貪心（dp）

我們枚舉 K，看 K 固定時需要多少次反轉次數，最直覺的寫法是：

for (int i = 0; i <= N - K; i++)
    if (dir[i] is 'B')
        flip A[i, i + K)
        cnt++

// check
for (int i = N - K + 1; i < N; i++)
    if (dir[i] is 'B')
        return -1;
return cnt

但時間複雜度是 O(n^3)，所以一定會 TLE。我們引入 dp 來優化

int f[i] = 1 if [i, i + K) 有反轉過 else 0

當我們想知道要不要反轉 [i, i + K) ，也就是要不要將 f[i] 設為 1 時， 我們可以透過計算 目前為止有函蓋到 dir[i] 的反轉次數 與 dir[i] 的值 來得出。

哪些區間反轉時會影響到 dir[i] 呢？觀察可得是

[f(x) | i - K + 1 <= x <= i]

這些區間

寫成式子：

Let F[i] = 影響到 dir[i] 的區間的反轉次數和
         = sum([f(x) | i - K + 1 <= x <= i])

F[i] 存在轉移方程式（可由觀察得出）：

F[i+1] = F[i] - f[i - K + 1] + f[i]

假設

dir[i] = 1 if dir[i] is 'F' else 0

則 dir[i] + F[i] 是奇數的話，就代表我們需要反轉 [i, i + K)

引入這此東西來優化，可得到文末的程式碼，時間複雜度降到 O(n^2);

AC code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

int N;
int dir[5000];
int f[5000];

int calc(const int K) {
    memset(f, 0, sizeof(f));
    int cnt = 0;
    int sum = 0; // dir[i] 的翻轉次數 = F[i]
    for (int i = 0; i <= N - K; i++) {
        // whether flipping [i, i + K)
        if ((dir[i] + sum) % 2 == 1) { // 是反面，翻轉 [i, i + K)
            cnt++;
            f[i] = 1;
        }
        // update sum: sum' = sum - f[i - K + 1] + f[i]
        sum += f[i];
        if (i - K + 1 >= 0)
            sum -= f[i - K + 1];
    }

    // 檢查剩下的 [N-K+1, N) 牛有否都已朝正面
    for (int i = N - K + 1; i < N; i++) {
        if ((dir[i] + sum) % 2 == 1) { // 否，無解
            return -1;
        }
        // update sum
        if (i - K + 1 >= 0)
            sum -= f[i - K + 1];
    }

    return cnt;
}

void solve() {
    int K = 1, M = N;
    for (int k = 1; k <= N; k++) {
        int cnt = calc(k);
        if (cnt != -1 && cnt < M) {
            M = cnt;
            K = k;
        }
    }

    printf("%d %d\n", K, M);
}

int main() {
    scanf("%d\n", &N);
    for (int i = 0; i < N; i++) {
        char c; scanf("%c\n", &c);
        dir[i] = ((c == 'F') ? 0 : 1);
    }
    solve();
    return 0;
}

dir[i] = 1 if dir[i] is 'F' else 0这一句是不是手误写反了？似乎应该是dir = 0 if dir[i] is 'F' else 0