题目链接： 传送门
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; int m, n, mx, a[N], dp[N], g[N]; int main() { while(scanf("%d%d",&m, &n)!=EOF) { //输入数据 for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } //初始化数组 memset(dp, 0, sizeof(dp)); memset(g, 0, sizeof(g)); //枚举选择字段的数量 for(int i = 1; i <= m; i++) { mx = -0x3f3f3f3f; //枚举前j段的最优解 for(int j = i; j <= n; j++) { dp[j] = max(dp[j - 1], g[j - 1])+ a[j]; //存下前i - 1个数中只拿j - 1份物品的最优解 g[j - 1] = mx; //更新获取本轮结果中的最优解 mx = max(mx, dp[j]); } } //输出结果 printf("%d\n", mx); } return 0; }这道题可以用动态规划来做 首先分析一下基本情况，该问题可以从n，m入手进行划分，设i，j两个变量用来分别表示前n个数和前m个选取方案。即分别枚举1，2，3，4，5……个数字的情况下，取子段1个，2个，3个……的情况，根据这个分析，我们很明显就能构思到一个二重循环的结构了，那接下来细节要怎么实现 首先最简单的就是开一个二维dp数组然后枚举上述讲的情况，找到了拆分集合，现在我们就要思考状态的转移方程是什么。其实这道题有两个状态dp[i][j - 1] + a[j] 和 max(dp[i - 1][k] + a[i])。前者表示在取了j个子段后再把i拿上合并到第j组字段中去，而第二个式子则是指拿了j - 1一个字段后，拿上当前第i个数字作为第j个子段。 大致思路清楚了记下来就是优化了，因为我们如果开个二维数组消耗会很大，因此我们可以把这个数组优化为一维，我们只需要记录i - 1个数字时的最优取法，和当前取法往右合并两种状态即可，因此，我们们可以开个数组，分别表示i - 1时每个状态的最大值，转移方程就会变为**dp[j] = max(dp[j - 1], g[j - 1])+ a[j]**具体每次的更新操作，可以看看代码及注释。
