题解：P10914 [蓝桥杯 2024 国 B] 跳石头

· · 题解

P10914 [蓝桥杯 2024 国 B] 跳石头

前置芝士：

需要了解 bitset 和动态规划的运用。

题目大意：

小明在第 i 个石头上可以跳到第 i+c_j 石头上或者跳到第 2\times i 块石头上，他在位置 i 得到的分数是他可以跳到的点的权值的不同的个数，要求他所得到的最高分。

题目思路：

用 1 表示可以跳到的节点，用 0 表示跳不到的节点，我们可以把它想象成一个二进制数，把每个可以跳到的节点用 bitset 合并起来，最后求每一次循环中的 bitset 中有多少个 1 的最大值就是结果。

代码：

#include<bits/stdc++.h>      
using namespace std;
int n;                          // 总位置数
int c[40500];                // 存储每个位置的分数值(注意实际题目场景可能需要调整数组大小)
int ans;                        // 存储最终结果(最大不同分数数量)
bitset<40500> dp[40500];        // dp[i]记录从位置i出发能获得的所有分数集合(注意n>10000会导致越界)
signed main() {
    std::ios::sync_with_stdio();
    cout.tie(0); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];           
    }

    // 逆向动态规划处理
    for(int i = n; i >= 1; i--) { // 从后往前处理，确保后续位置已计算
        dp[i][c[i]] = 1;        // 标记当前位置自身的分数值
        // 跳跃规则1：向右跳c[i]步
        if(i + c[i] <= n) {
            // 合并跳跃后的分数集合(位运算取并集)
            dp[i] |= dp[i + c[i]]; 
        }

        // 跳跃规则2
        if(i * 2 <= n) {
            // 合并跳跃后的分数集合
            dp[i] |= dp[i * 2]; 
        }

        // 更新最大不同分数数量
        ans = max(ans, int(dp[i].count())); // count()统计bitset中1的个数
    }

    cout << ans;                
    return 0;
}