Ответ 1
Попробуйте решить проблему с помощью динамического программирования.
Примечание. Если k > n, мы можем использовать только n интервалов.
Рассмотрим d [i] [j] решение задачи, когда S = {s 1,..., s i} и k = j. Поэтому легко видеть, что:
- d [0] [j] = 0 для каждого j от 1 до k
- d [i] [1] = sum (s 1... s i) для каждого я от 1 до n
- d [i] [j] = min для t = 1 до i (max (d [i - t] [j - 1], sum (s я - t + 1... s i)) для я = 1 до n и j = 2 к k
Теперь давайте посмотрим, почему это работает:
- Когда в последовательности нет элементов, ясно, что только один интервал может быть (пустой) и сумма его элементов равна 0. То, что d [0] [j] = 0 для всех j из 1 к k.
- Когда может быть только один интервал, ясно, что решение является суммой всех элементов последовательности. Итак, d [i] [1] = sum (s 1... s i).
- Теперь рассмотрим, что в последовательности есть я элементов, а число интервалов равно j, мы можем предположить, что последний интервал (s я - t + 1... s i), где t - положительное целое число, не большее i, поэтому в этом случае решение max (d [i - t] [j - 1]), sum (s я - t + 1...s i), но поскольку мы хотим, чтобы решение было минимальным, мы должны выбрать t таких, чтобы минимизировать его, поэтому мы получим min для t = 1 до i (max (d [i - t] [j - 1], sum (s я - t + 1... s i)).
Пример:
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;
}