解题思路

• 这是一个“只能向前、每次采摘至多一次”的路径规划问题。由于走格子只会消耗苹果、采摘只会增加苹果，苹果数的峰值只可能出现在起点或某次采摘之后。

• 设苹果林为下标从 1 到 m 的数组 A[i]。从起点到第 i 格需消耗 i 个苹果；从已采摘的第 j 格走到更靠前的第 i 格需消耗 i-j 个苹果。到达时苹果可以为 0（但此时不能继续前进一步，正好在该格采摘）。

• 动态规划：

  • 定义 dp[t][i]：恰好进行了 t 次采摘且第 t 次在第 i 格后，采摘完成时手上的最大苹果数；不可达则为负无穷。
  • 初始转移（从起点直接到第 i 格并采摘一次）：若 n >= i，则 dp[1][i] = n - i + A[i]。
  • 一般转移（从已在 j 格完成第 t-1 次采摘的状态到 i 格进行第 t 次采摘）：

题目内容

小红出门采苹果，前方 $m$ 个格子代表 $m$ 片苹果林，每个格子中的数字代表可采苹果的数量。

小红出门带了 $n$ 个苹果，只能往前走，需要消耗掉 $1$ 个苹果才能踏上一个格子。

小红最多进行 $k$ 次苹果采摘，每个格子最多采摘一次，请问小红苹果数最多的时候有几个苹果?

注意:可以不走上格子;苹果为 $0$ 时无法走上新的格子。

输入描述

第一行为 $m、n、k$ ，空格隔开

第二行为 $m$ 个整数，代表 $m$ 个格子上的苹果数，苹果数范围 $[0,20]$ ，空格隔开

$m、n、k$ 都为正整数，范围 $[1,20]$

输出描述

最多的苹果数

样例1

**输入

5 5 1
0 0 2 1 1

输出

5

说明

小红不踏上格子，不进行采摘的情况下苹果数最多，为 $5$ 个

样例2

输入

10 3 2
0 0 3 4 7 8 9 10 11 12

输出

8

说明

走到第 $3$ 格时，消耗了 $3$ 个苹果，进行第一次采摘获得 $3$ 个苹果，剩余苹果 $3$ 个

接下来走到第 $5$ 个格子，又消耗了 $2$ 个苹果，进行第二次采摘获得 $7$ 个苹果，剩余 $8$ 个苹果，在后面的格子进行采摘结果也一样。

故小红最多的时候有 $8$ 个苹果。