输出格式

输出到标准输出。

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

样例1输入

10 5
1 3 5 3 1

样例1输出

16

样例1解释

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

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

样例2输入

4 3
1 60 100

样例2输出

120

样例2解释

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

子任务

4040 的测试数据保证：n≤50n≤50 且 m=5m=5；

另有 4040 的测试数据保证：n=60n=60 且 m=6m=6；

全部测试数据保证：0<n≤1040<n≤104、0<m≤1000<m≤100 且 0≤Ai≤1050≤Ai​≤105。

 题解：只过了题目样例，并未实测

#include <bits/stdc++.h>
using namespace std;
int happy[100];
int dp[100];
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> happy[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (i - j >= 0)
            {
                dp[i] = max(dp[i], dp[i - j] + happy[j]);
            }
            else
                break;
        }
    }
    cout << dp[n] << endl;
}