[GXPC-S 2024] 分糖果

Luogu
IDLGB4168
Time1000ms
Memory512MB
DifficultyP4
动态规划 DP2024广西
有 $n$ 包糖果从左到右依次排成一行,第 $i$ 包糖果中有 $a_i$ 个糖果。小林和小伊从左到右对 $n$ 包糖果进行分配,分配权一开始在小林手里,小林可以将 $n$ 包糖果中最左端的糖果分配给自己或者小伊,本次分配中**没有拿到糖果**的人将拥有下一次的分配权。 如果小林和小伊都足够聪明,会采用最优的策略进行分配,保证自己最后拥有的糖果总数最多,如此分配 $n$ 轮后,求出小林和小伊中**糖果更多的那个人**所拥有的糖果数量。 ## Input 输入共 $2$ 行。 第一行包含一个整数 $n$,表示一共有 $n$ 包糖果。 第二行包含 $n$ 个整数,第 $i$ 个数 $a_i$ 表示第 $i$ 包糖果中的糖果数量。 ## Output 输出一行一个整数,表示小林和小伊中任一人可以获得的最大收益。 [samples] ## Background 小林最近迷上了博弈问题。 ## Note 样例解释:如下是他们的游戏过程。 - 小林将 $1$ 分给自己;此时小林和小伊的糖果数分别为 $1,0$; - 小伊将 $3$ 分给小林;此时小林和小伊的糖果数分别为 $4,0$; - 小伊将 $5$ 分给自己;此时小林和小伊的糖果数分别为 $4,5$; - 小林将 $7$ 分给小伊;此时小林和小伊的糖果数分别为 $4,12$; - 小林将 $9$ 分给自己;此时小林和小伊的糖果数分别为 $13,12$。 可以证明这是最优的游戏策略。 **本题采用捆绑测试。** - Subtask 1(40pts):保证 $n\le 20$; - Subtask 2(60pts):无额外约束。 对于 $100\%$ 的数据,保证 $1\le n,a_i\le 10^5$。
Samples
Input #1
5
1 3 5 7 9
Output #1
13
API Response (JSON)
{
  "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$ 轮后,求出小林和小伊中*...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments