Poj 3185: The Water Bowls

poj3185.md

Poj 3185: The Water Bowls

題目

分析

上一題 poj 3276 的簡化（K=3）與小變形（首尾可反轉二個）

相當於只能反轉連續三個， 並且反轉區間的頭從 -1 開始直到 N-2（不是 N-3）， 也就是說，在前面多補一項。 這樣只需枚舉第 -1 項的值，0 或 1 ，取所需反轉次數較小者。

實作時，儲存陣列全部向後平移一格。

AC code

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

using namespace std;

const int N = 21;
int dir[20 + 1];
int f[20 + 1];

int solve(int head_value) {
    memset(f, 0, sizeof(f));
    int cnt = 0;
    int sum = 0;
    dir[0] = head_value;
    for (int i = 0; i <= N - 3 + 1; i++) {
        if ((dir[i] + sum) % 2 == 1) {
            cnt++;
            f[i] = 1;
        }
        sum += f[i];
        if (i - 3 + 1 >= 0)
            sum -= f[i - 3 + 1];
    }

    if ((dir[N-1] + sum) % 2 == 1)
        return 0x3f3f3f3f;
    return cnt;
}

int main() {
    dir[0] = -1;
    for (int i = 1; i < N; i++)
        scanf("%d", &dir[i]);
    printf("%d\n", min(solve(0), solve(1)));

    return 0;
}