解题思路

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

• 设苹果林为下标从 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 次采摘）： 若 dp[t-1][j] >= i-j，则 dp[t][i] = max(dp[t][i], dp[t-1][j] - (i-j) + A[i])。

• 答案为 max(n, max_{1<=t<=k, 1<=i<=m} dp[t][i])，即起点不动与所有可达采摘后的峰值二者取最大。

• 算法：二维动态规划（区间/有序选择 + 可达性约束）。

复杂度分析

• 状态数 O(k*m)，每个状态枚举前一个采摘格 j，转移 O(m)，总时间复杂度 O(k * m^2)；在约束 m,k ≤ 20 下足够快。
• 额外空间复杂度 O(k * m)。

代码实现

Python

# 题目功能放在函数里，主函数只做输入输出（ACM风格）
import sys

INF_NEG = -10**9

def solve(m, n, k, arr):
    # 将数组改为1-based，便于计算步数
    A = [0] + arr
    # dp[t][i]：恰好t次采摘，最后一次在i格，采摘后手中最多苹果
    dp = [[INF_NEG]*(m+1) for _ in range(k+1)]
    ans = n  # 起点不动也可能是最大值

    # 第一次采摘：从起点直接走到i
    for i in range(1, m+1):
        if n >= i:
            dp[1][i] = n - i + A[i]
            if dp[1][i] > ans:
                ans = dp[1][i]

    # 后续采摘
    for t in range(2, k+1):
        for i in range(1, m+1):
            best = INF_NEG
            for j in range(1, i):
                if dp[t-1][j] >= i - j:  # 有能力走到i
                    cand = dp[t-1][j] - (i - j) + A[i]
                    if cand > best:
                        best = cand
            dp[t][i] = best
            if best > ans:
                ans = best

    return ans

def main():
    data = sys.stdin.read().strip().split()
    m, n, k = map(int, data[:3])
    arr = list(map(int, data[3:3+m]))
    print(solve(m, n, k, arr))

if __name__ == "__main__":
    main()

Java

// ACM风格：主类Main，主函数读写，核心逻辑在外部静态函数
import java.util.*;

public class Main {
    static final int INF_NEG = -1000000000;

    // 解决函数：返回最多时刻的苹果数
    static int solve(int m, int n, int k, int[] arr0) {
        int[] A = new int[m + 1]; // 1-based
        for (int i = 1; i <= m; i++) A[i] = arr0[i - 1];

        int[][] dp = new int[k + 1][m + 1];
        for (int t = 0; t <= k; t++) Arrays.fill(dp[t], INF_NEG);

        int ans = n; // 起点不动

        // 第一次采摘：从起点到i
        for (int i = 1; i <= m; i++) {
            if (n >= i) {
                dp[1][i] = n - i + A[i];
                if (dp[1][i] > ans) ans = dp[1][i];
            }
        }

        // 后续采摘
        for (int t = 2; t <= k; t++) {
            for (int i = 1; i <= m; i++) {
                int best = INF_NEG;
                for (int j = 1; j < i; j++) {
                    if (dp[t - 1][j] >= i - j) {
                        int cand = dp[t - 1][j] - (i - j) + A[i];
                        if (cand > best) best = cand;
                    }
                }
                dp[t][i] = best;
                if (best > ans) ans = best;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt(), k = sc.nextInt();
        int[] arr = new int[m];
        for (int i = 0; i < m; i++) arr[i] = sc.nextInt();
        System.out.println(solve(m, n, k, arr));
        sc.close();
    }
}

C++

// ACM风格：主函数读写，核心逻辑放在独立函数
#include <bits/stdc++.h>
using namespace std;

const int INF_NEG = -1000000000;

// 解决函数：返回最多时刻的苹果数
int solve(int m, int n, int k, const vector<int>& arr0) {
    vector<int> A(m + 1, 0); // 1-based
    for (int i = 1; i <= m; ++i) A[i] = arr0[i - 1];

    vector<vector<int>> dp(k + 1, vector<int>(m + 1, INF_NEG));
    int ans = n; // 起点不动

    // 第一次采摘：从起点到i
    for (int i = 1; i <= m; ++i) {
        if (n >= i) {
            dp[1][i] = n - i + A[i];
            ans = max(ans, dp[1][i]);
        }
    }

    // 后续采摘
    for (int t = 2; t <= k; ++t) {
        for (int i = 1; i <= m; ++i) {
            int best = INF_NEG;
            for (int j = 1; j < i; ++j) {
                if (dp[t - 1][j] >= i - j) {
                    int cand = dp[t - 1][j] - (i - j) + A[i];
                    best = max(best, cand);
                }
            }
            dp[t][i] = best;
            ans = max(ans, best);
        }
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m, n, k;
    if (!(cin >> m >> n >> k)) return 0;
    vector<int> arr(m);
    for (int i = 0; i < m; ++i) cin >> arr[i];
    cout << solve(m, n, k, arr) << "\n";
    return 0;
}

题目内容

小红出门采苹果，前方 $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$ 个苹果。