백준 1006번 - 습격자 초라기(증명)

On this page

https://www.acmicpc.net/problem/1006

Problem model

There are two rows of enemy units arranged in a circle of N columns. One squad covers either one cell, or two adjacent cells whose enemy counts sum to at most W. Find the minimum number of squads that covers every cell. Adjacent cells can be horizontal neighbors in one row (including columns N and 1) or the two cells in one column.

The circular edges are the only obstacle to a straightforward profile DP. We handle them by enumerating four possibilities: use neither wraparound pair, use the top pair, use the bottom pair, or use both. A chosen wraparound pair is fixed in advance; its two endpoint cells are removed from the remaining problem. The cells that remain form a linear strip, which takes only a constant number of DP states per column.

Linear profile DP

For a fixed choice of wraparound pairs, let forced[c] be a two-bit mask of cells already covered in column c. Bit 0 denotes the top row and bit 1 the bottom row. Only column 0 and column N-1 can have forced cells. The number of squads used by the chosen wrap pairs is added to the result after solving the strip.

Process columns from left to right. A DP state at the start of column c is a two-bit incoming mask: cells already covered by horizontal squads coming from column c-1. Reject a state if an incoming cell overlaps a forced cell. Otherwise begin filling the column with incoming | forced[c].

To fill a column, take its first uncovered cell and try each possible covering action:

• Cover it alone (one squad).
• If it is the top cell, cover both cells in this column with one squad when their sum is at most W.
• Cover it together with the same-row cell in the next column when their sum is at most W. This marks that next cell in the outgoing mask. Do not create this horizontal pair if that next cell is already forced by the selected wrap pair.

When both cells are covered, relax the next column’s DP state using the outgoing mask. Each column has only four masks and each fill has at most two cells, so this is O(N) time and O(N) memory. The four wrap choices only multiply the work by a constant.

For N = 1, there are no distinct horizontal neighbors: the only possible pair is the vertical pair in the sole column. Return one squad if its sum is at most W, otherwise two. Handle this separately so the two ends of a one-column circle are not mistaken for two different cells.

For N >= 2, test a selected top wrap pair only when top[0] + top[N-1] <= W, and likewise for the bottom row. The no-wrap choice is always considered. For each allowed choice, endpoint masks prevent any other squad from covering those cells, and the linear DP covers everything else. This also handles N = 2: an endpoint cell already consumed by a selected wrap pair cannot be paired again along the linear edge.

C++17 implementation

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N, W;
        cin >> N >> W;
        vector<array<int, 2>> enemy(N);
        for (int r = 0; r < 2; ++r)
            for (int c = 0; c < N; ++c)
                cin >> enemy[c][r];

        if (N == 1) {
            cout << (enemy[0][0] + enemy[0][1] <= W ? 1 : 2) << '\n';
            continue;
        }

        const int INF = 1e9;
        int answer = INF;

        // Enumerate wrap pairs: bit 0 = top, bit 1 = bottom.
        for (int wrap = 0; wrap < 4; ++wrap) {
            bool valid = true;
            int wrapCost = 0;
            vector<int> forced(N, 0);
            for (int r = 0; r < 2; ++r) {
                if ((wrap >> r) & 1) {
                    if (enemy[0][r] + enemy[N - 1][r] > W) {
                        valid = false;
                        break;
                    }
                    forced[0] |= 1 << r;
                    forced[N - 1] |= 1 << r;
                    ++wrapCost;
                }
            }
            if (!valid) continue;

            // dp[incoming mask] = minimum squads before filling this column.
            array<int, 4> dp{0, INF, INF, INF};
            for (int c = 0; c < N; ++c) {
                array<int, 4> next{INF, INF, INF, INF};
                for (int incoming = 0; incoming < 4; ++incoming) {
                    if (dp[incoming] == INF || (incoming & forced[c])) continue;
                    int occupied = incoming | forced[c];

                    auto fill = [&](auto&& self, int mask, int outgoing, int cost) -> void {
                        if (mask == 3) {
                            next[outgoing] = min(next[outgoing], dp[incoming] + cost);
                            return;
                        }
                        int row = (mask & 1) ? 1 : 0;
                        int bit = 1 << row;

                        // Use one squad for this cell alone.
                        self(self, mask | bit, outgoing, cost + 1);

                        // Cover the two cells in this column together.
                        if (row == 0 && mask == 0 &&
                            enemy[c][0] + enemy[c][1] <= W) {
                            self(self, 3, outgoing, cost + 1);
                        }

                        // Pair this cell with the same row in the next column.
                        if (c + 1 < N && !(outgoing & bit) &&
                            !(forced[c + 1] & bit) &&
                            enemy[c][row] + enemy[c + 1][row] <= W) {
                            self(self, mask | bit, outgoing | bit, cost + 1);
                        }
                    };
                    fill(fill, occupied, 0, 0);
                }
                dp = next;
            }
            answer = min(answer, dp[0] + wrapCost);
        }

        cout << answer << '\n';
    }
}

The recurrence is exhaustive because, at each step, the first uncovered cell must be covered alone, vertically with the other cell in its column, or horizontally with the next column. Each action is allowed only when all cells it uses are still available and a two-cell squad satisfies the capacity limit. The profile therefore represents every valid tiling without overlap, while each transition adds exactly one squad. Minimizing over the four possible wrap-pair selections covers every circular arrangement.