蓝桥杯2024年第十五届决赛真题-跳石头

小明正在和朋友们玩跳石头的小游戏，一共有 n 块石头按 1 到 n 顺序排成一排，第 i 块石头上写有正整数权值 c_i。

如果某一时刻小明在第 j 块石头，那么他可以选择跳向第 j + c_j 块石头（前提 j + c_j ≤ n）或者跳向第 2j 块石头（前提 2 j ≤ n），没有可跳跃的目标时游戏结束。

假如小明选择从第 x 块石头开始跳跃，如果某块石头有可能被小明经过（“经过” 指存在某一时刻小明在这个石头处），则将这块石头的权值纳入得分集合 S_x，那么小明从第 x 块石头开始跳跃的得分为 |S_x|。

比如如果小明从第 x 块石头出发，所有可能经过的石头上的权值分别为5, 3, 5, 2, 3，那么 S x = {5, 3, 2} 得分为 |S_x| = 3。小明可以任选一块石头开始跳跃，请求出小明最多能获得的分数。

输入共 2 行。第一行为一个正整数 n。第二行为 n 个由空格分开的正整数 c₁, c₂, . . . , c_n。

输出共 1 行，一个整数表示答案。

5
4 3 5 2 1

4

【样例说明】

从第一块石头出发得分最多，路径有以下几种：

1. 1号 → 5 号：选择从 1 号跳到 1 + c1=5 号。

2. 1 号 → 2 号 → 5 号：第一次选择从 1 号跳到 2 × 1=2 号，第二次选择从2 号跳到 2 + c2 = 5 号。

3. 1 号 → 2 号 → 4 号：第一次选择从 1 号跳到 2 × 1=2 号，第二次选择从2 号跳到 2 × 2 = 4 号

所以所有可能经过的石头的权值的集合为 S 1 = {c₁, c_2, c₄, c₅} = {4, 3, 2, 1}，得分为 |S₁| = 4。

【评测用例规模与约定】

对于 20% 的评测用例，保证 n ≤ 20。

对于 100% 的评测用例，保证 n ≤ 40000，c_i ≤ n。