C++2234: 划分集合

Question

2234: 划分集合
[命题人 : zyz-admin]
时间限制 : 5.000 sec 内存限制 : 128 MB

题目描述
一个有n个正整数元素的集合，要求把它划分成k部分，使每部分元素和的最大值最小， 求这个最小值。
输入
输入第一行两个正整数n，k
第二行为此集合ai
输出
输出一行一个数，为题目所求答案
样例输入
5 2
2 1 3 4 5
样例输出
8
提示
30%数据 n <= 30, k <= 10
100%数据 n <= 100000, k <= 5000, 0<=ai <= 10^9

#include<bits/stdc++.h>
using namespace std;
int main() {
    cout<<8;
}

Answer 1

引自免费微信小程序：皆我百晓生。

使用动态规划方法，记录前i个元素划分成j部分的最大和，然后选择合适的划分策略。