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

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

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

30

pts）

错误的开始：天真 DP 尝试

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

CPP

#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

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

CPP

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

问题所在：

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

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

位运算基础知识

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

CPP

// 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. 重复计数问题

CPP

// 考虑这个图：
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

位的二进制数：

第 $0$ 位：是否选择当前节点 $i$
第 $1$ 位：是否选择节点 $i+1$
...
第 $k-1$ 位：是否选择节点 $i+k-1$

CPP

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

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

核心洞察：由于

k

步限制，当我们处理节点

i

时：

所有可能产生重复访问冲突的节点都在 $\{i, i+1, \dots, i+k-1\}$ 这个窗口内
窗口外的节点要么还没被考虑，要么已经安全地处理完毕

状态转移的物理意义

CPP

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);
}

转移过程的直观理解：

CPP

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

这就像一个滑动窗口，始终跟踪当前决策点附近

k

个节点的访问情况。

正解代码详解

CPP

/*致谢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;
}

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

https://cdn.luogu.com.cn/upload/image_hosting/rysuec6p.png

状态设计的精妙解释

假设

k=3

，当前处理节点

i

：

CPP

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

状态转移：

CPP

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

让我重新解释：

实际上，状态

s

表示的是在当前决策时，未来 $k$ 步内节点的选择情况。当我们从节点

i

转移到节点

i-1

时：

原来考虑 $i, i+1, i+2, \dots, i+k-1$
现在考虑 $i-1, i, i+1, \dots, i+k-2$

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

完整输出示例

对于样例输入：

CPP

程序输出：

CPP

验证：

从节点 $1$ ：路径 $1 \to 2 \to 4$ 和 $1 \to 3 \to 4$ ，访问 $\{1,2,3,4\}$ ，总和 $= 3+4+5+1=13$ ✓
从节点 $2$ ：路径 $2 \to 4$ ，访问 $\{2,4\}$ ，总和 $= 4+1=5$ ✓
从节点 $3$ ：路径 $3 \to 4$ ，访问 $\{3,4\}$ ，总和 $= 5+1=6$ ✓
从节点 $4$ ：只能访问自己，总和 $= 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

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

文章操作

错误的开始：天真 DP 尝试

改进尝试：拓扑排序 DP

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

位运算基础知识

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

问题本质分析

1. 重复计数问题

2. 状态爆炸问题

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

为什么 $k$ 小如此重要？

数学证明

位运算 DP 的巧妙设计

状态定义的精妙之处

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

状态转移的物理意义

正解代码详解

状态设计的精妙解释

完整输出示例

总结对比

个人分享：

相关推荐

评论

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

文章操作

错误的开始：天真 DP 尝试

改进尝试：拓扑排序 DP

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

位运算基础知识

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

问题本质分析

1. 重复计数问题

2. 状态爆炸问题

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

为什么 kkk 小如此重要？

数学证明

位运算 DP 的巧妙设计

状态定义的精妙之处

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

状态转移的物理意义

正解代码详解

状态设计的精妙解释

完整输出示例

总结对比

个人分享：

相关推荐

评论

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

为什么 $k$ 小如此重要？