题目背景：

众所周知，西西艾弗岛上的机器人喜欢吃苹果。

题目描述：

据饲养员小 P 介绍：

机器人一天最多可以吃 𝑚个苹果。一天内通过吃苹果获得的快乐值具体为：𝐴0,𝐴1,⋯,𝐴𝑚；如果某一天饲养员共投喂机器人𝑖个苹果，则这一天机器人获得的快乐值为A𝑖。特别地 𝐴0=0，快乐值并不会凭空产生。

现在小 P 有 𝑛个苹果，试帮助小 P 计算：向机器人投喂这 𝑛个苹果能获得的最大快乐值收益。

输入格式

从标准输入读入数据。

输入共两行。

第一行包含两个整数 𝑛 和 𝑚，分别表示苹果总数和每天最大投喂量。第二行依次包含 𝑚 个整数 𝐴1,𝐴2,⋯,𝐴𝑚 ，表示一天内投喂不同苹果数的收益。

输出格式

输出到标准输出。

输出仅一个整数，表示投喂全部 𝑛个苹果能获得的最大收益。

样例1输入

10 5

1 3 5 3 1

样例1输出

16

样例1解释

一种最优投喂方案为：投喂四天，每天分别投喂 3、3、1 和 3 个苹果。

如该样例所示，收益序列 𝐴 不一定单调递增，即一天内吃较多苹果可能反而获得较小快乐值。

样例2输入

4 3

1 60 100

样例2输出

120

样例2解释

一种最优投喂方案为：投喂两天，每天投喂 2个苹果。

子任务

40 的测试数据保证：𝑛≤50 且 𝑚=5；

另有 40 的测试数据保证：𝑛=60且 𝑚=6；

全部测试数据保证：0<𝑛≤、0<𝑚≤100 且 0≤𝐴𝑖≤。

解题思路

这是一个完全背包问题。

考虑：用dp[n]来表示喂n个苹果所能得到的最大收益。

状态转移方程：求解dp[i]

需要考虑的是：

1、i从1开始，到n结束，最多投喂n个苹果

2、递归遍历的是：当最后一次投喂j个苹果时，它所对应的最大收益值。此时：j的取值范围为：1<=j<=i，因为一天投喂i个苹果（此时需注意i一定是小于m的，因为一天最多投喂m个），选择投喂j个苹果，这时它前面已经投喂了i-j个苹果，这i-j个苹果所对应的最大收益值为：dp[i-j]，用dp[i-j]+a[j]投喂最后一次时选择投喂j的最大值，此时比较dp[i]和dp[i-j]+a[j]的值，最大即为最大收益值。

所以状态方程为：dp[i] = max(dp[i], dp[i-j]+a[j])

代码如下：

#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

const int N = 10010;

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	int A[N], dp[N];
	for(int i = 1; i <= m; i ++ ){
		scanf("%d", &A[i]);
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = 1; j <= i; j ++ ){
			dp[i] = max(dp[i], dp[i-j] + A[j]);
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}

恭喜你，又解锁了一道新题目！

这里是希望你越来越好的XQY_小全全，一起加油吧！欢迎评论区讨论做题方法！