蓝桥杯跳石头题解：图论建模与bitset优化动态规划

1. 项目概述：从“跳石头”到图论建模

最近在带学生备赛蓝桥杯，刷到这道P10914“跳石头”，发现它是个非常典型的图论建模问题，但内核又比普通的DFS/BFS搜索多了一层“集合去重”的思考。题目描述了一个简单的游戏规则：一排编号1到n的石头，每块石头i有一个权值c_i。你站在石头j上，可以跳到石头j + c_j（如果不超过n），或者跳到石头2j（如果不超过n）。游戏从某块石头x开始，所有可能被经过的石头（注意是“可能”，意味着存在至少一条从x出发能到达该石头的路径）的权值构成一个集合S_x，得分就是这个集合的大小|S_x|。你需要找到从哪块石头开始，能获得最大的得分。

初看这题，很多同学会下意识地想：“这不就是从一个起点出发，在图上做DFS或BFS，把所有能到达的点找出来，然后统计它们权值的不重复个数吗？”这个思路方向是对的，但直接这么干，在n最大40000的情况下，如果对每个起点都做一次完整的图遍历，时间复杂度会爆炸。我们需要更聪明的办法。这道题的精髓在于，它虽然要求我们枚举所有可能的起点，但整个跳跃规则构建出的图结构是有规律的，我们可以利用动态规划（DP）或记忆化搜索，从后往前递推，一次性算出所有起点的答案，将复杂度降到O(n)或O(n log n)级别。接下来，我就结合C++实现，拆解一下这道题的解题思路、核心算法以及编码中的那些坑。

2. 核心思路拆解与算法选型

2.1 问题本质：可达性分析与权值集合

首先，我们要彻底理解题目在问什么。得分不是路径上权值之和，也不是最长路径，而是从起点x出发，所有可能到达的节点的权值集合的大小。这里有两个关键点：

1. “可能”到达：只要存在一条从x到石头y的路径（无论这条路径怎么跳），那么石头y就算被“经过”了。这意味着我们需要计算的是节点的可达性，而不是某一条特定路径。
2. 权值集合：多个不同的节点可能拥有相同的权值，但得分只计算一次。所以，我们最终关心的是所有可达节点的权值种类数。

因此，问题的核心可以分解为两步：对于每个起点x，计算出所有从x出发可达的节点集合；然后，统计这些节点对应权值的不重复数量。

2.2 暴力搜索的局限性

最直接的暴力方法是：对于每个起点i (1 <= i <= n)，执行一次图遍历（DFS或BFS），标记所有能从i到达的节点，然后遍历这些节点，用一个set<int>或unordered_set<int>来记录权值，最后集合的大小就是得分。再取所有得分的最大值。

我们来估算一下复杂度。对于每个起点，最坏情况下可能需要遍历整个图（虽然由于跳跃规则限制，图是稀疏的）。假设平均每个节点能到达m个其他节点，那么一次遍历的复杂度是O(m)。对于n个起点，总复杂度就是O(n * m)。在n=40000时，如果m也接近n，那就是O(n²) ≈ 1.6e9，显然会超时。题目给了20%的数据n<=20，可能就是给暴力搜索留的活路，但要想AC，必须优化。

2.3 优化方向：记忆化搜索与逆向思维

暴力法之所以慢，是因为它做了大量重复计算。考虑两个起点x和y，如果从x出发能到达y，那么从x出发能到达的所有节点，一定也包含从y出发能到达的所有节点（因为到了y之后，你可以继续从y开始的所有可能跳跃）。更一般地，这个跳跃关系构成了一个有向图。如果我们定义reachable[i]为一个集合，表示从石头i出发所有可能到达的节点集合，那么对于任意一条边 i -> j，都有reachable[i]包含{i} ∪ reachable[j]。

这启发我们可以用记忆化搜索（Memoization）或动态规划（DP）的思路，从后往前（或者用DFS+记忆化）来计算每个节点的reachable集合。但直接存储集合本身仍然可能很大，导致空间和时间开销大。

进一步观察，我们最终需要的不是节点集合，而是权值集合的大小。而且，权值c_i的范围也是1到n。一个更巧妙的思路是：我们能否直接计算出，从每个节点i出发，能收集到的不同权值有哪些？

这里需要引入状态压缩的思想。因为n<=40000，我们无法用一个长度为n的bool数组来为每个起点存储所有可能的权值（那样是O(n²)空间）。但是，我们可以换一个角度：用位运算或布尔数组记录“当前从某个节点出发，已经覆盖了哪些权值”，但这在传递时依然复杂。

实际上，更普适且清晰的思路是：先构建整个图的可达性关系，再利用“可达性”来推导“权值可达性”。具体有两种主流方法：

1. 传递闭包 + 权值统计：计算出图的传递闭包（即任意两点是否可达），然后对于每个起点i，将所有可达点j的权值c_j加入集合。但计算传递闭包（例如用Floyd-Warshall）是O(n³)，完全不可行。由于图是稀疏的且有特殊结构，我们需要更高效的闭包计算。
2. 记忆化搜索 + 集合合并：用DFS从每个未访问的节点开始搜索，在回溯过程中，将后继节点的可达权值集合合并到当前节点。合并操作（尤其是集合去重）是开销所在。

考虑到n=40000，c_i<=n，一个可行的优化是：用bitset来表示一个节点可达的权值集合。bitset<N>可以在常数时间内进行位运算（如或运算|），合并两个集合非常快。N=40001的bitset大小约为40001/8 ≈ 5KB。对于40000个节点，如果每个节点都存一个bitset，总内存约40000 * 5KB ≈ 200MB，这通常超过了竞赛题目的内存限制（通常256MB或512MB）。但我们可以利用动态bitset（如vector<bool>）或更紧凑的表示方法，不过实现起来较复杂。

2.4 最终算法确定：反向建图 + BFS/DFS + 差分思想

我查阅了网上一些AC的题解，并结合自己的思考，发现这道题有一个被忽略的突破口：跳跃规则是确定的，从每个点出发的出边最多只有两条（j+c_j 和 2j）。因此，整个图是一个每个节点出度最多为2的有向图。对于这样的图，我们可以考虑反向建图。

什么是反向建图？原图是如果从j能跳到k，就有一条边 j->k。反向建图则是，如果从j能跳到k，我们建立一条边 k->j。这意味着，在反向图中，如果有一条边 k->j，表示从j可以到达k（在原图中）。

为什么要反向建图？因为题目要求的是“从x出发能到达哪些点”，这等价于“在反向图中，从哪些点出发能到达x”。但这样似乎没简化问题。关键点在于：如果我们能预处理出所有节点通过反向边能到达的节点（即原图中能到达它的节点），然后利用这些信息来快速计算每个起点的得分吗？

一个精妙的做法是：从后往前动态规划。定义dp[i]为一个bitset或布尔数组，表示从节点i出发，能访问到的权值集合（用一个位掩码表示）。但如前所述，直接存bitset可能内存过大。

更进一步的优化是：我们并不需要为每个节点存储完整的权值集合，只需要知道从该节点出发，能访问到的权值种类数。但这样在合并时无法去重。

实际上，本题最简洁高效的AC解法是：进行一遍DFS或BFS，但配合一个全局的访问标记数组，并利用递归返回值来传递信息。然而，由于图可能有环（比如从i跳到j，又从j跳回i），直接DFS会陷入死循环，需要处理环。

综合来看，一个经过验证的可行算法步骤如下：

1. 建图：根据规则，为每个节点i建立两条有向边：i -> i+c_i (如果i+c_i <= n) 和 i -> 2i (如果2i <= n)。
2. 计算可达节点集：对于每个节点i，我们需要知道从i出发能到达的所有节点。这可以通过对每个节点i进行BFS/DFS实现，但这样是O(n²)。优化方法是：进行一次拓扑排序（如果图是无环的）或强连通分量缩点（如果图有环）。但我们的图由于有边i->2i，很可能存在环（例如1->2->4->1? 不一定，但需要检查）。实际上，由于c_i是正整数，且跳跃总是向编号更大的节点（i+c_i > i, 2i > i 当 i>=1），所以这个图是一个有向无环图（DAG）！因为每条边都是从编号小的节点指向编号大的节点。这是一个非常重要的性质！
3. 在DAG上动态规划：既然图是DAG，我们就可以按照节点编号从大到小的顺序进行动态规划。定义f[i]为一个集合，表示从节点i出发，能经过的节点的权值集合。由于是DAG，我们可以从后往前（从n到1）递推：
   • 初始化f[i]为只包含自身权值c_i的集合。
   • 对于节点i，它的后继节点是j1 = i + c_i(如果<=n) 和j2 = 2*i(如果<=n)。
   • 那么，从i出发能经过的权值集合，等于{c_i}并上f[j1]并上f[j2]（如果后继存在）。
   • 即f[i] = {c_i} ∪ f[j1] ∪ f[j2]。
4. 集合的表示与合并：我们需要高效地合并集合。由于权值范围是1~n，我们可以用一个bitset来表示集合。bitset<40001> f[i]表示集合，第k位为1表示权值k在集合中。那么合并操作就是位或运算：f[i] = f[i] | f[j1] | f[j2]。同时设置f[i][c_i] = 1。
5. 统计答案：计算完所有f[i]后，f[i].count()就是从i出发的得分。遍历所有i，取最大值即可。

复杂度分析：

• 时间：我们需要处理n个节点，每个节点最多合并两个bitset。bitset的位或运算可以认为是O(N/word_size)，在C++中bitset的位运算通常被优化为O(N/64)。N=40001，所以一次合并约625次64位运算。对于每个节点进行两次合并，总运算量约为n * 2 * (40001/64) ≈ 40000 * 2 * 625 = 50,000,000次操作，在1秒内可以完成。
• 空间：需要存储n个bitset，每个约5KB，总内存约200MB。这处于极限边缘，但通常蓝桥杯环境的内存限制可能为256MB或512MB，200MB是可行的，但有些风险。如果内存超限，我们可以尝试用vector<bitset<40001>>，但实际内存占用差不多。一个更好的优化是：**由于我们是从后往前递推，当计算完f[i]后，f[j](j>i) 可能不再需要，但f[i]在计算更小的i时可能还需要（因为边指向更大的j）。所以不能立即释放。内存是主要瓶颈。

注意：这是基于bitset的解法。在实际竞赛中，如果内存限制较紧（如128MB），可能需要更节省内存的方法，例如用vector<int>存储每个节点可达的权值列表，并用哈希表去重，但合并操作会更耗时。或者，可以采用BFS从每个节点出发，但用一个全局的bitset作为访问标记（标记权值），但这样需要n次BFS，每次BFS重置bitset，时间复杂度O(n²/64)可能也能勉强通过（40000*40000/64 ≈ 25e6次位操作），但不如DP优雅。

考虑到蓝桥杯国赛的难度和常见环境，bitset解法是通行的。下面我们就按照这个思路来实现。

3. 代码实现与逐行解析

3.1 数据结构定义与输入处理

首先，我们包含必要的头文件，并定义最大常数。由于n最大40000，权值c_i也<=n，我们把bitset的大小设为40001（索引从1到40000）。

#include <iostream> #include <vector> #include <bitset> #include <algorithm> using namespace std; const int MAXN = 40005; // 稍微开大一点，防止边界问题 int main() { int n; cin >> n; vector<int> c(n + 1); // 权值数组，下标从1开始 for (int i = 1; i <= n; ++i) { cin >> c[i]; } // 后续代码... }

这里定义c数组时大小是n+1，是为了让下标从1开始，与题目描述一致。

3.2 核心DP数组初始化

我们需要一个vector来存储每个节点的bitset。注意，bitset的大小必须在编译时确定，所以我们用bitset<MAXN>，其中MAXN=40005。

vector<bitset<MAXN>> f(n + 1); // f[i] 表示从节点i出发能经过的权值集合 // 初始化：每个节点至少能经过自身的权值 for (int i = 1; i <= n; ++i) { f[i].set(c[i]); // 将c[i]对应的位设为1 }

bitset的set(pos)函数将第pos位设置为1。注意，bitset的位索引默认从0开始，但我们的权值范围是1~n，所以直接使用c[i]作为索引是没问题的，因为c[i]>=1。当然，更严谨的做法是f[i].set(c[i])，这会将第c[i]位设为1。

3.3 动态规划递推过程

由于图是DAG（边从小节点指向大节点），我们可以从大到小遍历节点i，这样当处理节点i时，它的后继节点i+c[i]和2*i（如果存在）一定大于i，它们的f值已经计算好了。

for (int i = n; i >= 1; --i) { // 处理第一种跳法：跳到 i + c[i] int j1 = i + c[i]; if (j1 <= n) { f[i] |= f[j1]; // 合并集合：位或运算 } // 处理第二种跳法：跳到 2*i int j2 = 2 * i; if (j2 <= n) { f[i] |= f[j2]; } }

这里的关键操作是f[i] |= f[j1]，这是一个bitset的位或赋值操作，效果是将f[j1]中所有为1的位，在f[i]中也设为1。这样就实现了集合的合并。注意，我们之前已经将f[i]的c[i]位设为1，所以这里不需要再额外添加自身权值。

重要细节：为什么从后往前遍历？ 因为对于任意节点i，它的后继节点j1 = i+c[i] 和 j2 = 2*i 都满足 j1 > i 且 j2 > i（当i>=1时）。所以，当我们从i=n开始递减遍历到1时，对于当前的i，它的后继节点j1和j2的编号都大于i，因此它们的f值已经在之前的迭代中计算完成了。这满足了动态规划的“无后效性”。

3.4 统计答案并输出

递推完成后，f[i]这个bitset中1的个数，就是从节点i出发能获得的分值。我们遍历所有i，找出最大值。

int ans = 0; for (int i = 1; i <= n; ++i) { int score = f[i].count(); // 计算bitset中1的个数，即集合大小 if (score > ans) { ans = score; } } cout << ans << endl;

bitset的count()函数返回其中设置为1的位的数量，时间复杂度是O(N/word_size)，对于40001位来说很快。

3.5 完整代码整合

将以上部分整合，得到完整代码：

#include <iostream> #include <vector> #include <bitset> #include <algorithm> using namespace std; const int MAXN = 40005; // 预留一点空间 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); // 加速输入输出 int n; cin >> n; vector<int> c(n + 1); for (int i = 1; i <= n; ++i) { cin >> c[i]; } // dp数组，f[i]是一个bitset，表示从i出发能经过的权值集合 vector<bitset<MAXN>> f(n + 1); // 初始化：每个节点至少能经过自身的权值 for (int i = 1; i <= n; ++i) { f[i].set(c[i]); } // 从后往前DP，因为图是DAG（边从小节点指向大节点） for (int i = n; i >= 1; --i) { int j1 = i + c[i]; if (j1 <= n) { f[i] |= f[j1]; } int j2 = 2 * i; if (j2 <= n) { f[i] |= f[j2]; } } // 统计答案 int ans = 0; for (int i = 1; i <= n; ++i) { ans = max(ans, (int)f[i].count()); } cout << ans << endl; return 0; }

4. 算法正确性证明与边界情况

4.1 为什么这个DP是正确的？

我们需要证明：按照上述递推公式计算出的f[i]，确实等于从节点i出发，所有可能经过的节点的权值集合。

定义：设S(i)为从节点i出发，所有可能经过的节点的权值集合。

归纳基础：对于节点i，如果它没有出边（即i+c[i] > n且2*i > n），那么从i出发只能停留在i，所以S(i) = {c[i]}。我们的初始化f[i].set(c[i])正好对应这一点。

归纳步骤：假设对于所有编号大于i的节点j，f[j]已经正确计算并等于S(j)。考虑节点i，它最多有两个后继：j1 = i+c[i]和j2 = 2*i。从i出发，第一步有两种选择：跳到j1或跳到j2（如果合法）。如果跳到j1，那么之后所有可能经过的节点就是从j1出发能经过的节点；同理，如果跳到j2，之后所有可能经过的节点就是从j2出发能经过的节点。此外，无论怎么跳，起点i本身也会被经过。因此，从i出发所有可能经过的节点集合是：{i}加上 从j1出发能经过的节点 加上 从j2出发能经过的节点。对应的权值集合就是：{c[i]}∪S(j1)∪S(j2)。根据归纳假设，f[j1] = S(j1),f[j2] = S(j2)。而我们递推中的操作f[i] |= f[j1]; f[i] |= f[j2];（在已经设置f[i][c[i]]=1的基础上）正好计算了这个并集。所以f[i]也正确。

由于我们是从大到小遍历i，所以归纳假设成立，DP正确。

4.2 边界情况与注意事项

1. 数组越界：在访问j1 = i + c[i]和j2 = 2*i时，必须检查是否小于等于n。我们的代码中用了if (j1 <= n)和if (j2 <= n)来保护。
2. 权值作为bitset索引：权值c[i]的范围是1~n，我们直接用c[i]作为bitset的索引。这要求bitset的大小至少为n+1。我们定义了MAXN=40005，足够容纳。
3. 内存使用：这是本解法最大的潜在问题。vector<bitset<MAXN>> f(n+1)占用的内存大约是(n+1) * (MAXN/8) bytes。代入n=40000, MAXN=40005，约为40001 * 5000 ≈ 200MB。这接近但通常不超过蓝桥杯国赛的内存限制（常为256MB）。如果担心内存超限，可以尝试用bitset<40001>而不是bitset<MAXN>，但这样需要确保n<=40000。或者，可以使用vector<bool>来模拟bitset，但vector<bool>不是标准容器，位操作可能慢一些。
4. 时间复杂度：DP循环是O(n)，每次循环中进行两次bitset的位或运算。bitset的位或运算复杂度是O(N/word_size)，即O(40000/64)≈O(625)。所以总时间大约是40000 * 2 * 625 ≈ 50,000,000次位操作，这在2秒内通常可以完成。

5. 性能优化与替代方案

虽然上述bitsetDP解法是主流且易于理解的，但在极端情况下（内存限制更紧或n更大时）可能需要优化。这里讨论几种变体：

5.1 使用vector<bool>替代bitset

bitset的大小必须在编译时确定，这不够灵活。我们可以用vector<bool>来动态创建位集，每个vector<bool>只存储从该节点出发可达的权值集合。但vector<bool>的位运算不支持直接对整个容器进行位或，需要手动循环，或者用std::transform，但效率可能较低。

vector<vector<bool>> f(n + 1, vector<bool>(n + 1, false)); // 初始化 for (int i = 1; i <= n; ++i) f[i][c[i]] = true; // DP递推 for (int i = n; i >= 1; --i) { int j1 = i + c[i], j2 = 2 * i; if (j1 <= n) { for (int k = 1; k <= n; ++k) { if (f[j1][k]) f[i][k] = true; } } if (j2 <= n) { for (int k = 1; k <= n; ++k) { if (f[j2][k]) f[i][k] = true; } } } // 统计答案 int ans = 0; for (int i = 1; i <= n; ++i) { int cnt = 0; for (int k = 1; k <= n; ++k) cnt += f[i][k]; ans = max(ans, cnt); }

这种方法的复杂度是O(n²)，对于n=40000来说是16亿次操作，显然会超时。所以不可取。

5.2 BFS/DFS + 全局权值标记

另一种思路是：从每个节点i开始做BFS或DFS，用一个全局的bool visited[N]数组来标记本次搜索中哪些权值已经出现过。每次BFS前清空visited数组。统计本次搜索中访问到的不同权值数量。

vector<int> c(n+1); vector<vector<int>> graph(n+1); // 邻接表 // 建图 for (int i = 1; i <= n; ++i) { if (i + c[i] <= n) graph[i].push_back(i + c[i]); if (2 * i <= n) graph[i].push_back(2 * i); } int ans = 0; vector<bool> visited_val(n+1, false); // 标记权值是否已计入 for (int start = 1; start <= n; ++start) { fill(visited_val.begin(), visited_val.end(), false); queue<int> q; q.push(start); visited_val[c[start]] = true; int count = 1; // 至少包含起点权值 while (!q.empty()) { int u = q.front(); q.pop(); for (int v : graph[u]) { if (!visited_val[c[v]]) { visited_val[c[v]] = true; count++; } q.push(v); // 注意：即使权值已访问过，节点仍需入队继续探索，因为可能通过该节点到达其他权值未访问的节点 } } ans = max(ans, count); }

这个算法的时间复杂度是O(n * (V+E))，其中V是节点数，E是边数。最坏情况下每个节点都可达几乎所有其他节点，所以近似O(n²)，也会超时。但我们可以加上节点访问标记来剪枝：如果某个节点已经被访问过，那么从该节点出发能到达的权值集合已经被合并到当前集合中，可以不再重复探索。然而，由于我们关心的是权值集合，即使节点被访问过，它的权值可能已经被记录，但通过它可能到达的新节点（权值未记录）仍需探索。所以不能简单用节点访问标记来剪枝。因此，BFS方法在n=40000时难以通过。

5.3 基于拓扑排序的DP

既然图是DAG，我们可以先进行拓扑排序，然后按照拓扑序从后往前DP。不过由于节点编号天然满足拓扑序（边从小节点指向大节点），所以直接按编号从大到小遍历就是拓扑序，不需要显式进行拓扑排序。我们的解法已经利用了这一点。

5.4 内存优化技巧

如果内存是瓶颈，我们可以尝试不存储所有节点的完整bitset，而是用时间换空间。例如，对于每个节点i，我们只存储一个vector<int>，表示从i出发能到达的权值列表，并在合并时去重。但合并两个列表并去重的时间复杂度较高。或者，我们可以用哈希表（unordered_set）来存储权值集合，但内存开销也不小。

一个折中的方案是：使用bitset，但分批处理。例如，将权值范围分成若干块（比如每块大小1000），对每块分别进行DP。具体地，我们进行多次DP，每次只关心权值在某个区间内的节点。最后合并结果。但这样需要多次遍历，时间可能增加。

考虑到蓝桥杯的环境，bitset解法在大多数情况下是可以通过的。如果遇到内存超限，可以尝试将bitset改为vector<bool>，但使用引用或指针来减少拷贝，或者尝试用int数组模拟位运算。

6. 常见错误与调试技巧

在实现和调试这道题时，我遇到过一些典型的错误，这里列出来供大家参考：

1. 数组下标越界：这是最常见的错误。在计算j1 = i + c[i]和j2 = 2*i时，一定要检查是否<= n。另外，c数组和f数组的大小应该是n+1，索引从1开始。
2. bitset大小不足：bitset<N>的N必须是一个编译时常量，且N要大于等于可能出现的最大权值（即n）。如果n=40000，那么N至少需要40001。建议定义为const int MAXN = 40005;，留一点余量。
3. DP顺序错误：必须从后往前（从n到1）遍历。如果从前往后遍历，当计算f[i]时，它的后继节点f[j1]和f[j2]可能还没有计算（因为j1, j2 > i），导致使用未初始化的值。
4. 忘记初始化自身权值：在DP开始前，必须将每个f[i]的c[i]位设为1。否则，如果某个节点没有出边，它的得分会被错误地计算为0。
5. 内存超限：如果使用vector<bitset<MAXN>> f(n+1)，请估算内存。40000 * 40000 bit ≈ 200MB。如果题目内存限制是128MB，可能会超。这时可以考虑用short或bool数组来存储每个节点可达的权值集合，但需要更复杂的压缩。
6. 输出格式错误：题目要求输出一个整数，不要输出多余的空格或换行。
7. 输入读取优化：对于n=40000，输入量不大，但使用ios::sync_with_stdio(false); cin.tie(nullptr);可以加速输入输出，避免卡常。

调试技巧：

• 可以先用小数据测试，比如n=5，手动模拟DP过程，验证结果是否正确。
• 对于每个节点i，可以输出f[i].count()，检查得分是否合理。
• 如果怀疑DP顺序，可以打印出每个节点i的后继节点j1和j2，确保j1, j2 > i。
• 如果内存或时间超限，可以尝试用bitset的test()和set()函数来验证位操作是否正确。

7. 总结与扩展思考

这道“跳石头”题目看似是一个简单的游戏模拟，实则考察了对图论模型的抽象能力、对DAG上动态规划的应用，以及对bitset优化集合运算的掌握。通过这道题，我们可以学到：

1. 问题转化：将游戏规则转化为有向图，将得分计算转化为节点可达性与权值集合的并集。
2. 利用图的性质：识别出图是DAG（因为边总是从小节点指向大节点），从而可以使用基于拓扑序的DP。
3. bitset优化：当需要频繁合并集合，且集合元素是有限范围内的整数时，bitset可以通过位运算在常数时间内完成合并，极大提高效率。这是处理状态压缩和集合运算的利器。
4. 时空权衡：bitset解法用较大的内存（约200MB）换取了较低的时间复杂度（约5e7次位操作）。在竞赛中，这种权衡往往是必要的。

扩展思考：

• 如果跳跃规则改变，比如可以往回跳（例如跳到j - c[j]），那么图就可能包含环。这时就需要先用强连通分量（SCC）算法缩点，将环缩成一个点，然后在DAG上DP。
• 如果权值范围很大（比如10^9），就不能用bitset了。这时可能需要用哈希表（unordered_set）来存储集合，但合并操作会更耗时。或者，可以离线处理，用并查集维护连通性，再统计每个连通分量内不同权值的数量。
• 如果题目问的不是最大得分，而是从每个起点出发的得分，那么我们的DP已经计算出了所有起点的得分，直接输出即可。

最后，在竞赛中遇到这类题目，关键是先分析数据范围，再选择合适的算法。对于n=40000，O(n²)的暴力通常不可行，必须寻找O(n log n)或O(n * bit)的优化。bitsetDP是一个非常重要的技巧，值得熟练掌握。