机器人饲养指南

形式化题目

有 $n$ 个苹果需要分若干天投喂完。每天最多投喂 $m$ 个，若某天投喂 $i$ 个苹果获得快乐值 $A_i$ （ $1 \le i \le m$ ）。求把 $n$ 个苹果全部投喂完能获得的最大快乐值总和。

思路

每一天投喂的数量在 $[1, m]$ 内自由选择，天数不限，这正是一个完全背包问题：把"一天投喂 $i$ 个"看成一件重量为 $i$ 、价值为 $A_i$ 的物品，背包容量为 $n$ 。

朴素递归

先看一个直接枚举每天投喂数量的递归做法，它把问题拆成一层一层的选择：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:47
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> happiness;

// 递归枚举每天投喂的苹果数，remaining 表示还剩多少个苹果
long long dfs(int remaining) {
    if (remaining == 0) return 0;

    long long answer = -(1LL << 60);
    for (int today = 1; today <= min(m, remaining); today++) {
        answer = max(answer, happiness[today] + dfs(remaining - today));
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    happiness.assign(m + 1, 0);
    for (int i = 1; i <= m; i++) cin >> happiness[i];
    cout << dfs(n) << '\n';
    return 0;
}

递归中每天都枚举投喂 $1 \sim m$ 个苹果，并递归处理剩下的苹果。这种方法指数级增长，只适合小数据，但清楚地展示了状态的划分方式。

动态规划

设 $dp[i]$ 表示恰好投喂 $i$ 个苹果时的最大快乐值。考虑最后一天投喂 $j$ 个苹果（ $1 \le j \le \min(m, i)$ ），则前面 $i-j$ 个苹果的收益独立，于是有转移：

dp[i] = \max_{1 \le j \le \min(m, i)} (dp[i-j] + A_j)

初值 $dp[0]=0$ ，按 $i$ 从小到大递推即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:47
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<long long> happiness(m + 1, 0); // happiness[i] 表示一天投喂 i 个苹果的快乐值
    for (int i = 1; i <= m; i++) cin >> happiness[i];

    // dp[i] 表示恰好投喂 i 个苹果能获得的最大快乐值
    vector<long long> dp(n + 1, -(1LL << 60));
    dp[0] = 0;
    for (int apples = 1; apples <= n; apples++) {
        // 最后一天投喂 today 个，前面已经投喂 apples-today 个
        int limit = min(m, apples);
        for (int today = 1; today <= limit; today++) {
            dp[apples] = max(dp[apples], dp[apples - today] + happiness[today]);
        }
    }
    cout << dp[n] << '\n';
    return 0;
}

复杂度

每个状态 $dp[i]$ 枚举 $j$ 最多 $m$ 次，时间复杂度为 $O(nm)$ ，空间复杂度为 $O(n)$ 。

总结

每天的收益 $A_i$ 不要求单调递增，因此不能只选择收益最大的投喂数量。按"最后一天"划分状态可以完整枚举所有合法的分组方式，这正是完全背包的经典转移。

目录

形式化题目

思路

朴素递归

动态规划

代码

复杂度

总结