题解：P12687 [KOI 2022 Round 1] 鹅卵石

· · 题解

要解决这个问题，我们需要确定哲洙最少需要多少次操作才能拿走所有鹅卵石。关键是最大化使用操作 1（从相邻两个地点拿走相同数量的鹅卵石），因为它比操作 2（从单个地点拿走任意数量的鹅卵石）更高效。

解题思路

操作 1 可以一次处理两个相邻地点，效率更高，优先使用。操作 2 用于处理无法通过操作 1 处理的单个地点。

对于连续的地点序列，如果能完全通过操作 1 处理，所需操作 1 的次数等于该序列中 "有效操作" 的数量（即相邻地点间需要非零操作的次数）。

当连续序列无法完全通过操作 1 处理时，需要插入操作 2 点将序列分段，每个分段单独用操作 1 处理，总操作次数为各分段操作 1 次数加上操作 2 点数量。

对于连续的地点序列（如从第 l 到 r 个地点），需判断能否完全用操作 1 处理。

设处理 l 到 r 时，相邻两点间的操作 1 用量为d_1, d_2, ..., d_3(k = r-l)，其中 d_i 表示第l+i-1 与 l+i 点间取走的数量。d_1 必须等于 a_l（因为 l 点左侧无相邻点，只能通过 d_1 处理）。d_i = a[l+i-1] - d_{i+1}(i>1)，即中间点的数量由左右两侧的 d 共同决定。所有 d_i \geq 0（不能取负数鹅卵石）。

若满足以上条件，该段可完全用操作 1 处理，所需操作 1 次数为非零 d_i 的数量（每个非零 d_i 对应一次操作 1）。

预处理两个数组：

valid[l][r]：标记 l 到 r 的连续段是否满足上述条件。

cost[l][r]：若valid[l][r]为真，记录该段所需的操作 1 次数（非零 d_i 的数量）。

定义 dp[i] 为前 i 个地点中，第 i 个地点作为操作 2 点时的最少操作次数。

转移方程：对于每个 i，枚举之前的操作 2 点 j(0 \leq j < i)，则 j+1 到 i-1 构成一段连续区间。若该区间有效（valid[j+1][i-1] 为真），则 dp[i] = min(dp[i], dp[j] + 1 + cost[j+1][i-1])（+1 是处理 i 点的操作 2，cost 是该段的操作 1 次数）。

预处理所有可能的连续序列，判断是否可通过操作 1 处理，并计算所需操作 1 次数。使用动态规划计算最少操作次数，dp[i]表示前 i 个地点中，第 i 个地点作为操作 2 点时的最少操作次数。

最终答案为所有可能分段方式的最小值。

代码实现

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> a(N + 1); 
    for (int i = 1; i <= N; ++i) {
        cin >> a[i];
    }
    vector<vector<bool> > v(N + 2, vector<bool>(N + 2, false));
    vector<vector<int> > cost(N + 2, vector<int>(N + 2, 0));

    for (int l = 1; l <= N; ++l) {
        v[l][l] = true;
        cost[l][l] = 1;
        if (l == N) continue;

        // 计算从l开始的连续段
        int d_p = a[l];  // d[0]，对应l和l+1之间的操作
        if (d_p < 0) continue;  // 初始d为负，后续无效
        int nn = (d_p != 0) ? 1 : 0;
        // 处理r = l+1的情况
        if (d_p == a[l + 1]) {
            v[l][l + 1] = true;
            cost[l][l + 1] = nn;
        } else {
            v[l][l + 1] = false;
        }
        // 处理r >= l+2的情况
        for (int r = l + 2; r <= N; ++r) {
            int poss = r - 1;  // d_c对应poss和r之间的操作
            int d_c = a[poss] - d_p;
            if (d_c < 0) break;  // 后续r都无效

            if (d_c != 0) {
                nn++;
            }

            // 检查是否满足最后一个条件：d_c == a[r]
            if (d_c == a[r]) {
                v[l][r] = true;
                cost[l][r] = nn;
            } else {
                v[l][r] = false;
            }

            d_p = d_c;
        }
    }

    // dp[i]：前i个地点，第i个是操作2点的最少操作次数
    vector<int> dp(N + 2, INT_MAX / 2);
    dp[0] = 0;  // 起点

    for (int i = 1; i <= N; ++i) {
        for (int j = 0; j < i; ++j) {
            int l = j + 1;
            int r = i - 1;

            if (l > r) {
                // 空段，只需j到i的操作2
                if (dp[j] + 1 < dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            } else {
                if (v[l][r]) {
                    if (dp[j] + 1 + cost[l][r] < dp[i]) {
                        dp[i] = dp[j] + 1 + cost[l][r];
                    }
                }
            }
        }
    }

    // 计算最终答案：考虑最后一段不是操作2点的情况
    int answer = dp[N];  // 最后一个是操作2点的情况
    for (int j = 0; j < N; ++j) {
        int l = j + 1;
        int r = N;
        if (v[l][r]) {
            answer = min(answer, dp[j] + cost[l][r]);
        }
    }

    cout << answer << endl;

    return 0;
}