专栏文章

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

NNancy_Cherry
P12687题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio0zx91
此快照首次捕获于
2025/12/02 11:35
3 个月前
此快照最后确认于
2025/12/02 11:35
3 个月前
查看原文
要解决这个问题，我们需要确定哲洙最少需要多少次操作才能拿走所有鹅卵石。关键是最大化使用操作 1（从相邻两个地点拿走相同数量的鹅卵石），因为它比操作 2（从单个地点拿走任意数量的鹅卵石）更高效。

解题思路

操作 11 可以一次处理两个相邻地点，效率更高，优先使用。操作 22 用于处理无法通过操作 11 处理的单个地点。
对于连续的地点序列，如果能完全通过操作 11 处理，所需操作 11 的次数等于该序列中 "有效操作" 的数量（即相邻地点间需要非零操作的次数）。
当连续序列无法完全通过操作 11 处理时，需要插入操作 22 点将序列分段，每个分段单独用操作 11 处理，总操作次数为各分段操作 11 次数加上操作 22 点数量。
对于连续的地点序列（如从第 ll 到 rr 个地点），需判断能否完全用操作 11 处理。
设处理 ll 到 rr 时，相邻两点间的操作 11 用量为d1,d2,...,d3(k=r−l)d_1, d_2, ..., d_3(k = r-l)，其中 did_i 表示第l+i−1l+i-1 与 l+il+i 点间取走的数量。d1d_1 必须等于 ala_l（因为 ll 点左侧无相邻点，只能通过 d1d_1 处理）。di=a[l+i−1]−di+1(i>1)d_i = a[l+i-1] - d_{i+1}(i>1)，即中间点的数量由左右两侧的 dd 共同决定。所有 di≥0d_i \geq 0（不能取负数鹅卵石）。
若满足以上条件，该段可完全用操作 11 处理，所需操作 11 次数为非零 did_i 的数量（每个非零 did_i 对应一次操作 11）。
预处理两个数组：
valid[l][r]：标记 ll 到 rr 的连续段是否满足上述条件。
cost[l][r]：若valid[l][r]为真，记录该段所需的操作 11 次数（非零 did_i 的数量）。
定义 dp[i] 为前 ii 个地点中，第 ii 个地点作为操作 22 点时的最少操作次数。
转移方程：对于每个 ii，枚举之前的操作 22 点 j(0≤j<i)j(0 \leq j < i)，则 j+1j+1 到 i−1i-1 构成一段连续区间。若该区间有效（valid[j+1][i-1] 为真），则 dp[i] = min(dp[i], dp[j] + 1 + cost[j+1][i-1])（+1+1 是处理 ii 点的操作 22，cost 是该段的操作 11 次数）。
  • 最后一个地点是操作 22 点，对应 dp[N]。
  • 最后一段（从 j+1j+1 到 NN）完全用操作 11 处理，此时总次数为 dp[j] + cost[j+1][N]（jj 为最后一个操作 22 点）。 取两种情况的最小值，即为最少操作次数。
预处理所有可能的连续序列，判断是否可通过操作 11 处理，并计算所需操作 11 次数。使用动态规划计算最少操作次数，dp[i]表示前 i 个地点中，第 i 个地点作为操作 22 点时的最少操作次数。
最终答案为所有可能分段方式的最小值。

代码实现

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...