{"problem":{"name":"[GXPC-S 2024] 分糖果","description":{"content":"有 $n$ 包糖果从左到右依次排成一行，第 $i$ 包糖果中有 $a_i$ 个糖果。小林和小伊从左到右对 $n$ 包糖果进行分配，分配权一开始在小林手里，小林可以将 $n$ 包糖果中最左端的糖果分配给自己或者小伊，本次分配中**没有拿到糖果**的人将拥有下一次的分配权。 如果小林和小伊都足够聪明，会采用最优的策略进行分配，保证自己最后拥有的糖果总数最多，如此分配 $n$ 轮后，求出小林和小伊中*","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4168"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 包糖果从左到右依次排成一行，第 $i$ 包糖果中有 $a_i$ 个糖果。小林和小伊从左到右对 $n$ 包糖果进行分配，分配权一开始在小林手里，小林可以将 $n$ 包糖果中最左端的糖果分配给自己或者小伊，本次分配中**没有拿到糖果**的人将拥有下一次的分配权。\n\n如果小林和小伊都足够聪明，会采用最优的策略进行分配，保证自己最后拥有的糖果总数最多，如此分配 $n$ 轮后，求出小林和小伊中**糖果更多的那个人**所拥有的糖果数量。\n\n## Input\n\n输入共 $2$ 行。\n\n第一行包含一个整数 $n$，表示一共有 $n$ 包糖果。\n第二行包含 $n$ 个整数，第 $i$ 个数 $a_i$ 表示第 $i$ 包糖果中的糖果数量。\n\n## Output\n\n输出一行一个整数，表示小林和小伊中任一人可以获得的最大收益。\n\n[samples]\n\n## Background\n\n小林最近迷上了博弈问题。\n\n## Note\n\n样例解释：如下是他们的游戏过程。\n\n- 小林将 $1$ 分给自己；此时小林和小伊的糖果数分别为 $1,0$；\n- 小伊将 $3$ 分给小林；此时小林和小伊的糖果数分别为 $4,0$；\n- 小伊将 $5$ 分给自己；此时小林和小伊的糖果数分别为 $4,5$；\n- 小林将 $7$ 分给小伊；此时小林和小伊的糖果数分别为 $4,12$；\n- 小林将 $9$ 分给自己；此时小林和小伊的糖果数分别为 $13,12$。\n\n可以证明这是最优的游戏策略。\n\n**本题采用捆绑测试。**\n\n- Subtask 1（40pts）：保证 $n\\le 20$；\n- Subtask 2（60pts）：无额外约束。\n\n对于 $100\\%$ 的数据，保证 $1\\le n,a_i\\le 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4168","tags":["动态规划 DP","2024","广西"],"sample_group":[["5\n1 3 5 7 9","13"]],"created_at":"2026-03-03 11:09:25"}}