「HOI R1」杂赛选比

Luogu
IDLGP10381
Time1000ms
Memory512MB
DifficultyP5
动态规划 DP线段树并查集2024O2优化洛谷比赛
给定一个长度为 $n$ 的数组 $a$,初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$,初始值为 $1$。现在小 $\iiint$ 在对这个数组进行一个游戏: - 如果 $a_i$ 未被解锁,游戏结束。 - 否则他可以将 $a_{i+1\sim i+a_i}$ 设置成已被解锁的,或是获得 $a_i$ 个金币(如果 $a_i=0$ 则无法解锁任何元素),然后将 $i$ 加 $1$。 请你求出游戏结束后你能获得的最大金币数量。 ## Input **本题有多组测试数据。** 第一行一个整数 $T$,表示测试数据组数。 对于每一组数据,第一行一个正整数 $n$。 接下来一行 $n$ 个非负整数 $a_{1\sim n}$。 ## Output 对于每一组数据,一行一个数,表示答案。 [samples] ## Background 你说得对,但是小 $\iiint$ 在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子,痛失 2h 遗憾离场,希望大家引以为戒。 ## Note #### 【样例 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$|/|
Samples
Input #1
3
2
1 2
5
2 4 5 0 1
4
0 4 4 4
Output #1
2
9
0
Input #2
1
10
1 1 4 5 1 4 1 9 1 9
Output #2
26
API Response (JSON)
{
  "problem": {
    "name": "「HOI R1」杂赛选比",
    "description": {
      "content": "给定一个长度为 $n$ 的数组 $a$,初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$,初始值为 $1$。现在小 $\\iiint$ 在对这个数组进行一个游戏: - 如果 $a_i$ 未被解锁,游戏结束。 - 否则他可以将 $a_{i+1\\sim i+a_i}$ 设置成已被解锁的,或是获得 $a_i$ 个金币(如果 $a_i=0$ 则无法解锁任何元素),然后将 $i$ 加 $1$。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10381"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的数组 $a$,初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$,初始值为 $1$。现在小 $\\iiint$ 在对这个数组进行一个游戏:\n\n- 如果 $a_i$ 未被解锁,游戏结束。\n- 否则他可以将 $a_{i+1\\sim i+a_i}$ 设置成已被解锁的,或是获得 $a_i$ 个金币(如果 $a_i=0$ 则无法解锁任何元素),然后将 $i$ 加 $1$。\n\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments