Оптимизация: разделите массив на непрерывные подпоследовательности длиной не выше k, так что сумма максимального значения каждой подпоследовательности минимальна

Оптимизируйте алгоритм O(n^2) до O(n log n).

Заявление о проблемах

Указанный массив A из n положительных целых чисел. Разделите массив на непрерывные подпоследовательности длиной не более k, так что сумма максимального значения каждой подпоследовательности минимальна. Вот пример.

Если n = 8 и k = 5, а элементы массива 1 4 1 3 4 7 2 2, лучшим решением является 1 | 4 1 3 4 7 | 2 2. Сумма будет max{1} + max{4, 1, 3, 4, 7} + max{2, 2} = 1 + 7 + 2 = 10.

O (n ^ 2) решение

Пусть dp[i] будет минимальной суммой, как в постановке задачи для массива подзадач A[0] ... A[i]. dp[0] = A[0] и, для 0 < i < n (dp[-1] = 0),

dp[i] = min(0, i-k+1 <= j <= i)(dp[j - 1] + max{A[j], ..., A[i]})

// A, n, k, - defined
// dp - all initialized to INF
dp[0] = A[0];
for (auto i = 1; i < n; i++) {
    auto max = -INF;
    for (auto j = i; j >= 0 && j >= i-k+1; j--) {
        if (A[j] > max)
            max = A[j];
        auto sum = max + (j > 0 ? dp[j-1] : 0);
        if (sum < dp[i])
            dp[i] = sum;
    }
}
// answer: dp[n-1]

O (n log n)?

Автор проблемы утверждал, что это можно было решить в O(n log n) времени, и есть некоторые люди, которые смогли передать тестовые примеры. Как это можно оптимизировать?

Ответы

Ответ 1

ПРИМЕЧАНИЕ. Я немного изменю ваше отношение к динамическому программированию, так что нет специального случая, если j = 0. Теперь dp[j] является ответом для первых j терминов A[0], ..., A[j-1] и:

dp[i] = min(dp[j] + max(A[j], ..., A[i-1]), i-k <= j < i)

Ответ проблемы теперь dp[n].

Обратите внимание, что если j < i и dp[j] >= dp[i], вам не понадобится dp[j] в следующих переходах, потому что max(A[j], ..., A[l]) >= max(A[i], ..., A[l]) (так что всегда лучше обрезать i вместо j.

Кроме того, пусть C[j] = max(A[j+1], ..., A[l]) (где l - наш текущий индекс на этапе динамического программирования, т.е. i в вашей программе на С++).

Затем вы можете сохранить в памяти некоторый набор индексов x1 < ... < xm ( "интересные" индексы для переходов вашего отношения к динамическому программированию), чтобы: dp[x1] < ... < dp[xm] (1). Затем автоматически C[x1] >= ... >= C[xm] (2).

Чтобы сохранить {x1, ..., xm}, нам нужна некоторая структура данных, которая поддерживает следующие операции:

  • Отбросить назад (когда мы переходим от i до i+1, мы должны сказать, что i-k теперь недоступен) или фронт (cf. insertion).
  • Нажимаем вперед x (когда мы вычислили dp[i], вставим его, сохранив (1), удалив соответствующие элементы).
  • Вычислить min(dp[xj] + C[xj], 1 <= j <= m).

Таким образом, будет достаточно одной очереди для хранения x1, ..., xk вместе с set для хранения всех dp[xi] + C[xi].

Как мы сохраняем (1) и обновляем C при вставке элемента i?

  • Перед вычислением dp[i] мы обновим C с помощью A[i-1]. Для этого найдем наименьший элемент xj в множестве x s.t. C[xj] <= A[i-1]. Тогда из (1) и (2) следует, что dp[j'] + C[j'] >= dp[j] + C[j] для всех j' >= j, поэтому мы обновляем C[xj] до A[i-1] и удаляем x(j+1), ..., xm из набора (*).
  • Когда мы вставляем dp[i], мы просто удаляем все элементы s.t. dp[j] >= dp[i], щелкнув спереди.
  • Когда мы удаляем i-k, возможно, что какой-то элемент, уничтоженный в (*), теперь становится лучше. Поэтому при необходимости мы обновляем C и вставляем последний элемент.

Сложность: O(n log n) (в наборе может быть не более 2n вставки).

В этом коде суммируются основные идеи:

template<class T> void relaxmax(T& r, T v) { r = max(r, v); }

vector<int> dp(n + 1);
vector<int> C(n + 1, -INF);
vector<int> q(n + 1);
vector<int> ne(n + 1, -INF);
int qback = 0, qfront = 0;
auto cmp = [&](const int& x, const int& y) {
    int vx = dp[x] + C[x], vy = dp[y] + C[y];
    return vx != vy ? vx < vy : x < y;
};
set<int, decltype(cmp)> s(cmp);

dp[0] = 0;
s.insert(0);
q[qfront++] = 0;

for (int i = 1; i <= n; ++i) {
    C[i] = A[i - 1];
    auto it_last = lower_bound(q.begin() + qback, q.begin() + qfront, i, [=](const int& x, const int& y) {
        return C[x] > C[y];
    });

    for (auto it = it_last; it != q.begin() + qfront; ++it) {
        s.erase(*it);
        C[*it] = A[i - 1];
        ne[*it] = i;
        if (it == it_last) s.insert(*it);
    }

    dp[i] = dp[*s.begin()] + C[*s.begin()];

    while (qback < qfront && dp[q[qfront]] >= dp[i]) {
        s.erase(q[qfront]);
        qfront--;
    }

    q[qfront++] = i;
    C[i] = -INF;
    s.insert(i);

    if (q[qback] == i - k) {
        s.erase(i - k);

        if (qback + 1 != qfront && ne[q[qback]] > q[qback + 1]) {
            s.erase(q[qback + 1]);
            relaxmax(C[q[qback + 1]], C[i - k]);
            s.insert(q[qback + 1]);
        }

        qback++;
    }
}

// answer: dp[n]

На этот раз я проверил его против вашего алгоритма: см. здесь.

Пожалуйста, дайте мне знать, если это все еще неясно.