P10381 「HOI R1」杂赛选比

你说得对，但是小 $\iiint$ 在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子，痛失 2h 遗憾离场，希望大家引以为戒。

给定一个长度为 $n$ 的数组 $a$，初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$，初始值为 $1$。现在小 $\iiint$ 在对这个数组进行一个游戏： - 如果 $a_i$ 未被解锁，游戏结束。 - 否则他可以将 $a_{i+1\sim i+a_i}$ 设置成已被解锁的，或是获得 $a_i$ 个金币（如果 $a_i=0$ 则无法解锁任何元素），然后将 $i$ 加 $1$。 请你求出游戏结束后你能获得的最大金币数量。

无

无

#### 【样例 1 解释】 对于第一组数据，你可以解锁 $a_2$，再获得 $a_2$ 个金币。而对于第三组数据，你无法解锁 $a_2$，因此只能获得 $0$ 个金币。 对于第二组数据，你可以解锁 $a_2,a_3$，并获得 $9$ 个金币。 #### 【样例 2 解释】 将第 $1,2,3,6$ 个位置用于解锁为最优方案。 #### 【数据范围】 对于 $100\%$ 的数据，$1\le n\le10^5$，$0\le a_i\le10^5$，$T\le 5$。 |测试点编号|$n\leq$|$a_i\leq$|$T=$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$0$|$1$|/| |$2\sim3$|$10$|$5$|$1$|/| |$4\sim5$|$600$|$600$|$1$|/| |$6\sim8$|$5000$|$5000$|$1$|/| |$9\sim10$|$10^5$|$5$|$5$|/| |$11\sim12$|$5\times10^4$|$10^5$|$5$|$a_i>n$| |$13\sim20$|$10^5$|$10^5$|$5$|/|