让我们尝试使用动态编程解决问题。

注意：如果 k > n，_我们只能使用 _n个 间隔。

让我们考虑 d [i] [j] 是当 S = { s 1，…， s i }和 k = j 时问题的解决方案。因此很容易看到：

1. 对于 从 1 到 k的 每个 j d [0] [j] = 0 __
2. d [I] [1] =总和（S 1 … S 我）_为每个 _我 从 1 到 Ñ
3. d [i] [j] = min 对于t = 1至i（max（d [i-t] [j-1]，sum（s i-t + 1 … s i））对于i = 1至n和j = 2至k

现在，让我们看看为什么它起作用：

1. 当序列中没有元素时，很明显只有一个间隔（空的一个），并且元素的总和为0。这就是为什么从 1 到 k的 所有 j的 d [0] [j] = 0 的原因。 __
2. 当只有一个间隔时，很明显，解决方案是序列中所有元素的总和。所以 d [i] [1] = sum（s 1 … s i）。
3. 现在让我们考虑序列中有 i个 元素，并且间隔数为 j ，我们可以假设最后一个间隔为（s i-t + 1 … s i），其中 t 是不大于 i的 正整数。案例解为 max（d [i-t] [j-1]，sum（s i-t + 1 … s i），但是由于我们希望解最小，因此我们应选择 t 这样将其最小化，因此我们将获得 分钟 对于t = 1到i（MAX（d [I - T] [J - 1]，和（š I - T + 1 … S 我）） 。

例：

S =（5,4,1,12），k = 2

d [0] [1] = 0，d [0] [2] = 0

d [1] [1] = 5，d [1] [2] = 5

d [2] [1] = 9，d [2] [2] = 5

d [3] [1] = 10，d [3] [2] = 5

d [4] [1] = 22，d [4] [2] = 12

码：

#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

int main ()
{
    int n;
    const int INF = 2 * 1000 * 1000 * 1000;
    cin >> n;
    vector<int> s(n + 1);
    for(int i = 1; i <= n; ++i)
        cin >> s[i];
    vector<int> first_sum(n + 1, 0);
    for(int i = 1; i <= n; ++i)
        first_sum[i] = first_sum[i - 1] + s[i];
    int k;
    cin >> k;
    vector<vector<int> > d(n + 1);
    for(int i = 0; i <= n; ++i)
        d[i].resize(k + 1);
    //point 1
    for(int j = 0; j <= k; ++j)
        d[0][j] = 0;
    //point 2
    for(int i = 1; i <= n; ++i)
        d[i][1] = d[i - 1][1] + s[i]; //sum of integers from s[1] to s[i]
    //point 3
    for(int i = 1; i <= n; ++i)
        for(int j = 2; j <= k; ++j)
        {
            d[i][j] = INF;
            for(int t = 1; t <= i; ++t)
                d[i][j] = min(d[i][j], max(d[i - t][j - 1], first_sum[i] - first_sum[i - t]));
        }


    cout << d[n][k] << endl;
    return 0;
}