{"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请你求出游戏结束后你能获得的最大金币数量。\n\n## Input\n\n**本题有多组测试数据。**\n\n第一行一个整数 $T$，表示测试数据组数。\n\n对于每一组数据，第一行一个正整数 $n$。\n\n接下来一行 $n$ 个非负整数 $a_{1\\sim n}$。\n\n## Output\n\n对于每一组数据，一行一个数，表示答案。\n\n[samples]\n\n## Background\n\n你说得对，但是小 $\\iiint$ 在打 CF 时将 Earn or Unlock 错看成了下面的鬼畜样子，痛失 2h 遗憾离场，希望大家引以为戒。\n\n## Note\n\n#### 【样例 1 解释】\n\n对于第一组数据，你可以解锁 $a_2$，再获得 $a_2$ 个金币。而对于第三组数据，你无法解锁 $a_2$，因此只能获得 $0$ 个金币。\n\n对于第二组数据，你可以解锁 $a_2,a_3$，并获得 $9$ 个金币。\n\n#### 【样例 2 解释】\n\n将第 $1,2,3,6$ 个位置用于解锁为最优方案。\n\n#### 【数据范围】\n\n对于 $100\\%$ 的数据，$1\\le n\\le10^5$，$0\\le a_i\\le10^5$，$T\\le 5$。\n\n|测试点编号|$n\\leq$|$a_i\\leq$|$T=$|特殊性质|\n|:-:|:-:|:-:|:-:|:-:|\n|$1$|$10$|$0$|$1$|/|\n|$2\\sim3$|$10$|$5$|$1$|/|\n|$4\\sim5$|$600$|$600$|$1$|/|\n|$6\\sim8$|$5000$|$5000$|$1$|/|\n|$9\\sim10$|$10^5$|$5$|$5$|/|\n|$11\\sim12$|$5\\times10^4$|$10^5$|$5$|$a_i>n$|\n|$13\\sim20$|$10^5$|$10^5$|$5$|/|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10381","tags":["动态规划 DP","线段树","并查集","堆","2024","O2优化","洛谷比赛"],"sample_group":[["3\n2\n1 2\n5\n2 4 5 0 1\n4\n0 4 4 4\n","2\n9\n0\n"],["1\n10\n1 1 4 5 1 4 1 9 1 9","26\n"]],"created_at":"2026-03-03 11:09:25"}}