题解：P12929 [POI 2022/2023 R2] 攀登 / Wspinaczka

· · 题解

这道题是竞赛教练 Aha 在版里举办 NOIP 模拟赛时的题目的原题（当时题目里改成了 APA（啊哈星球拍照协会）去爬 AhaMount）。

最后我此题成了此题的最高得分者（30 pts）

错误的开始：天真 DP 尝试

看到题目时，我第一反应是“这不就是个 DAG 最长路嘛！”于是兴冲冲地写下了这样的代码：

#include<iostream>
#include<vector>
#include<algorithm>
#define LL long long
using namespace std;

const int N=1e5+20;
LL n,m,k,a[N],ans[N];
vector<int> G[N];

// 天真的DFS+记忆化
LL dfs(int u, vector<bool>& visited){
    LL res = a[u];
    for(int v : G[u]){
        if(!visited[v]){
            visited[v] = true;
            res = max(res, a[u] + dfs(v, visited));
            visited[v] = false;
        }
    }
    return res;
}

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

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
    }

    // 对每个起点计算
    for(int i=1;i<=n;i++){
        vector<bool> visited(n+1,false);
        visited[i] = true;
        ans[i] = dfs(i, visited);
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

结果： 这个代码连样例都过不了！为什么？因为重复访问问题太复杂了。

改进尝试：拓扑排序 DP

然后我想：“用拓扑排序应该能解决重复计数问题吧？”

#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define LL long long
using namespace std;

const int N=1e5+20;
LL n,m,k,a[N],in[N],dp[N];
vector<int> G[N];
bitset<N> reach[N];  // 用bitset记录可达性

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

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        in[y]++;
    }

    // 拓扑排序
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(in[i]==0) q.push(i);
        reach[i][i] = 1;  // 自己可达自己
        dp[i] = a[i];
    }

    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : G[u]){
            // 合并可达集合
            bitset<N> new_reach = reach[u] | reach[v];
            LL new_val = 0;

            // 计算新价值 - 这里就出问题了！
            // 我们需要知道哪些节点在并集中，但无法高效计算
            for(int i=1;i<=n;i++){
                if(new_reach[i]) new_val += a[i];
            }

            if(new_val > dp[v]){
                dp[v] = new_val;
                reach[v] = new_reach;
            }

            if(--in[v] == 0) q.push(v);
        }
    }

    for(int i=1;i<=n;i++){
        cout<<dp[i]<<'\n';
    }
    return 0;
}

问题所在：

  1. bitset<N> 在 N=10^5 时太大
  2. 计算新价值需要遍历所有节点，复杂度 O(n^2)
  3. 内存爆炸，时间爆炸！

正解登场：位运算状态压缩 DP

位运算基础知识

在讲解正解前，先复习一下用到的位运算：

// 1. 设置第j位为1
state |= (1 << j);

// 2. 检查第j位是否为1  
if(state & (1 << j))

// 3. 右移一位（相当于除以2）
new_state = state >> 1;

// 4. 位掩码操作
mask = (1 << k) - 1;  // 得到k位全1的掩码

使用位运算 DP 的原因：为什么这是最佳选择？

问题本质分析

首先，让我们深入理解这个问题的核心难点：

1. 重复计数问题

// 考虑这个图：
1 → 2 → 4
1 → 3 → 4

如果简单地进行 DAG 上的 DP，节点 4 会被两条路径分别访问，导致重复计算。

2. 状态爆炸问题

我们需要记录已经访问过的节点集合，但 n 最大为 10^5 ，直接记录 2^n 个状态显然不可行。

关键突破口： k \leq 8 的限制

为什么 k 小如此重要？

由于任意路径连接的空地高度差不超过 k ，这带来了一个重要的局部性原理：

对于当前节点 i ，我们只需要关心未来 k 步内可能访问的节点，因为超过 k 步的节点在当前决策时还不会遇到重复访问问题。

数学证明

引理：在从节点 i 出发的任何路径中，如果两个节点 j 和 j' 都被访问，且 |j-j'| > k ，那么它们不可能在当前决策中产生冲突。

证明：因为路径只能向上，且单步跳跃不超过 k ，要访问距离超过 k 的节点，必须经过中间节点，这些中间节点会在状态转移过程中自然处理重复计数问题。

位运算 DP 的巧妙设计

状态定义的精妙之处

我们定义状态 s 为一个 k 位的二进制数：

// 状态s的含义（k=3为例）
// s = 1 0 1 表示：
// - 选择节点i   (第0位=1)
// - 不选节点i+1 (第1位=0)  
// - 选择节点i+2 (第2位=1)

为什么这个状态设计有效？

核心洞察：由于 k 步限制，当我们处理节点 i 时：

状态转移的物理意义

for(int i=n;i>=1;i--){
    for(int s=0;s<(1<<k);s++){
        LL new_state = (s >> 1);  // 窗口滑动
        if(s & 1) new_state |= b[i];  // 如果选择i，加入新边

        g[s] = f[new_state] + ((s & 1) ? a[i] : 0);
    }
    swap(f, g);
}

转移过程的直观理解：

时间点t：考虑节点i，状态s记录[i, i+k-1]的选择
时间点t+1：考虑节点i-1，状态右移 → 记录[i-1, i+k-2]的选择

这就像一个滑动窗口，始终跟踪当前决策点附近 k 个节点的访问情况。

正解代码详解

/*致谢C202301的巨佬题解，以及同班的Imik巨佬（AK CSP-J 2025）讲解*/
#include<iostream>
#define LL long long
using namespace std;

const int N=1e5+20;
LL n,m,k,a[N],b[N],f[1<<8],g[1<<8],ans[N];

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

    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    // 关键步骤1：用位掩码记录边信息
    for(int i=1;i<=m;i++){
        LL x,y;
        cin>>x>>y;
        // 将边(x,y)编码到位掩码中
        // 1LL<<(y-x-1) 表示从x出发，经过(y-x)步到达y
        b[x]|=(1LL<<(y-x-1));
    }

    int mask=(1<<k);  // 状态总数：2^k

    // 关键步骤2：倒序DP
    for(int i=n;i>=1;i--){
        LL bi=b[i],ai=a[i];
        //这里用到了4的位运算性质，代码长但成就了最优解（这里的规律可以推一下）
        // 循环展开优化：一次处理4个状态
        for(int s=0;s<mask;s+=4){
            // 状态s：不选当前节点i
            LL ns0=(s>>1);           // 状态右移
            g[s]=f[ns0];             // 直接继承

            // 状态s+1：选择当前节点i  
            LL ns1=((s+1)>>1);
            if((s+1)&1) ns1|=bi;     // 如果选择i，加入新的可达节点
            g[s+1]=f[ns1]+ai;        // 加上当前节点价值

            // 状态s+2：选择当前节点i
            LL ns2=((s+2)>>1);
            if((s+2)&1) ns2|=bi;
            g[s+2]=f[ns2]+ai;

            // 状态s+3：选择当前节点i
            LL ns3=((s+3)>>1);
            if((s+3)&1) ns3|=bi;
            g[s+3]=f[ns3]+ai;
        }

        // 处理剩余状态
        for(int s=(mask/4)*4;s<mask;s++){
            LL new_state=(s>>1);
            if(s&1) new_state|=bi;
            g[s]=f[new_state]+((s&1)?ai:0);
        }

        swap(f,g);          // 滚动数组
        ans[i]=f[1];        // f[1]表示选择当前节点i的状态
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<'\n';
    }
    return 0;
}

这是没加任何优化的全站最优解：

状态设计的精妙解释

假设 k=3 ，当前处理节点 i ：

状态s的二进制表示：b2 b1 b0
其中：
b0 = 1 表示选择节点i
b1 = 1 表示选择节点i+1  
b2 = 1 表示选择节点i+2

状态转移：

原状态s:   1 0 1  (选择i和i+2)
右移后:     1 0    (选择i+1和i+3？等等，这里需要仔细理解...)

让我重新解释：

实际上，状态 s 表示的是在当前决策时，未来 k 步内节点的选择情况。当我们从节点 i 转移到节点 i-1 时：

所以右移操作实际上是在“滑动窗口”！

完整输出示例

对于样例输入：

4 4 2
3 4 5 1
1 2
2 4  
1 3
3 4

程序输出：

13
5
6
1

验证：

总结对比

方法 时间复杂度 空间复杂度 能否 AC
天真 DFS O(2^n) O(n) ❌
拓扑 DP O(n^2) O(n^2) ❌
位运算 DP O(n \cdot 2^k) O(2^k) ✅

关键洞察： 当 k 很小时，状态压缩是解决此类问题的利器！这道题教会我们，有时候限制条件不是障碍，而是解题的钥匙。

个人分享：

官网：https://www.longzhuge.com.cn/

云盘：https://cloud.longzhuge.com.cn/

CSDN：lyx919

gitcode：https://gitcode.com/longzhuge