Имея отсортированную гистограмму из n баров, выберите k баров, минимизируя площадь, ограниченную правой стеной.

В дальнейшем я буду предполагать, что k >= 2, поскольку в противном случае проблема не решается тривиально.

Вот частичное решение в том смысле, что оно может решить часть проблемы за O(n) времени, если форма стержней имеет некоторые специфические свойства. В частности, мы можем сделать следующие выводы:

Если объем, покрываемый всеми барами, выпуклый, то оптимальное решение содержит только бары в начале и в конце.

Доказательство:

Предположим, что в решении есть какое-то разделение, тогда мы можем переместить группу, которая находится от одного из ребер, к одному из ребер. Это делается путем отмены выбора полосы с одной стороны и выбора новой с другой стороны. Так как форма выпуклая, кривизна должна быть неположительной, то при движении в невозрастающем направлении уменьшение при дальнейшем движении в этом направлении должно быть не меньше (кривизна это обеспечивает). Таким образом, мы можем переместить разбиение решения на одно из ребер без увеличения (и, вероятно, уменьшения) покрываемой площади.

Мы можем проверить за O(n) время, является ли фигура выпуклой (невозрастающая разница между полосами), и мы можем решить проблему с оптимизацией скользящего окна, что просто сделать в O(n). Таким образом, мы можем предварительно обработать любое другое решение, чтобы уменьшить набор задач до задачи, содержащей хотя бы одну вогнутую область. Если мы сможем найти подзадачи для других алгоритмов, которые также содержат это свойство, то мы также сможем решить их отдельно в этом смысле.

Для вогнутых областей они могут иметь стабильную внутреннюю область (куда могут притягиваться новые расщепления) в дополнение к внешним возможным стабильным областям (куда могут притягиваться другие расщепления, потому что, даже если разница в площади при таком перемещении положительный, движение все еще может быть отрицательным). Используя это, мы можем описать полностью вогнутую область участками, где расколы будут двигаться к краям или стабильной средней точке.

Обратите внимание, что многое из вышеперечисленного падает, когда вогнутые и выпуклые области соединены, поскольку критерии стабильности зависят от наличия границы в начале и конце, от которых мы измеряем. Хотя можно было бы решить всю проблему, опираясь на этот подход, я не уверен, насколько он поможет на произвольно сложных формах.

Требование к вогнутой области иметь внутреннюю стабильную область, как правило, довольно жесткое (в глобальном масштабе), и я не уверен, что вы вообще можете получить очень много из них в глобальном масштабе, поэтому вот алгоритм, который используйте это, чтобы решить проблему в O(n), O(kn) или O(kn^2), в зависимости от сложности проблемы, просматривая различные эвристики и переходя к более дорогой, если мы не уверены, что нашли оптимальное решение.

Сначала мы вычисляем базовый результат в режиме скользящего окна (O(n)) и сохраняем этот результат. Затем мы ищем области стабильности для одной точки (эти внешние области уже рассматриваются в скользящем окне), которая указывает в сторону от краев и имеет площадь, меньшую, чем найденное решение. Если таких точек более 1 (требуется специальная форма), по умолчанию возвращается базовый алгоритм, такой как у Маниша Чандры Джоши. Если найдена одна такая точка, мы переходим к решению O(nk), если нет, принимается текущее решение. Обратите внимание, что мы могли бы расширить приведенную ниже версию до более чем 1 такой точки глобальной стабильности, но на практике потребуется, чтобы они были достаточно близки, поскольку в противном случае они, как правило, позже обнаруживаются как сбои.

В решении «O(kn)» мы решаем скользящее окно отдельно по обе стороны от глобальной точки устойчивости посередине для каждого из kвозможных количеств назначений баров по обеим сторонам и выбираем лучшее из этих решений. . Затем мы снова ищем области стабильности внутри каждой из областей (помните, что это означает, что раскол не будет двигаться к ребру) и проверяем, соответствует ли площадь оптимальной из этих точек вместе с центральной точкой, которую мы вычисляем. for имеет меньшую площадь, чем меньшее из решений «O (kn)» и «O (n)». Если такая точка найдена, мы должны принять полное решение (как у Маниша Чандры Джоши), в противном случае мы можем принять лучшее из двух вычисленных нами решений.

Обратите внимание, что должна быть возможность включить большую граничную область как безопасную или легко выводимую из безопасного решения в приведенном выше алгоритме и, таким образом, увеличить количество случаев, когда мы не возвращаемся к более медленному алгоритму. В частности, область, удаленная примерно на «k» от края, может иметь простые решения или на практике уже быть покрыта более ранними решениями. Обратите внимание, что вычисляя скользящие окна как окна непокрытой области, мы должны иметь возможность генерировать некоторые простые решения для таких случаев в сочетании с данными из решений динамического программирования в случае «O (kn)».

Частичное решение Ninetails покрывает некоторую часть ответа, и я выяснил несколько других случаев, которыми я поделюсь.

У меня нет доказательств этого, но оптимальные бары, которые мы берем, всегда формируют ряды форм 1010, или 10, или 01, или 010, или 101, или тривиального 1. (Здесь 1 означает серию баров, которые мы взяли, а 0 означает серию баров, которые мы не взяли)

Это означает, что оптимальные стержни всегда находятся либо в одной непрерывной группе, либо в двух смежных группах, причем одна группа касается самого левого края. Я проверил этот факт, используя генератор случайных тестов с перебором O(2ⁿn²) и O(n²k ) решение для динамического программирования, запустив его для нескольких тысяч случаев.

Таким образом, с этим пониманием мы можем легко найти ответ за O (n * k), используя массив сумм префиксов для эффективного поиска сумм диапазонов. Вот окончательный код на С++ (с небольшими комментариями)

using ll = long long;
    ll n, z;
    cin >> n >> z;
    vector<ll> a(n);
    for (auto &e : a) {
        cin >> e;
    }
    assert(is_sorted(a.begin(), a.end()));

    ll stratAns, ans = INF;

    // prefix sum array
    vector<ll> pref(n + 1);
    for (int i = 1; i <= n; ++i) {
        pref[i] = pref[i - 1] + a[i - 1];
    }

    stratAns = INF;

    /// strategy 1 : handles cases where runs like 10, 01, 010, 1 are optimal to choose

    for (int starting = 0; starting + z - 1 < n; ++starting) {
        int ending = starting + z - 1;
        ll curAns = 0;

        //~ for (int i = starting; i <= ending; ++i) {
            //~ curAns += a[i];
        //~ }
        // doing the same with prefix sums instead
        curAns += pref[ending + 1] - pref[starting];

        curAns += a[ending] * (n - ending - 1);
        stratAns = min(stratAns, curAns);
    }
    ans = min(ans, stratAns);

    stratAns = INF;

    /// strategy 2 : handle cases when runs 1010 and 101 are optimal

    for (int last = z - 1; last < n; ++last) {
        for (int x = 1, y = z - 1; y > 0 && x < z; x++, y--) {
            assert(x + y == z);
            ll curAns = 0;

            //~ for (int i = 0; i < x; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[x];

            curAns += a[x - 1] * (last - y + 1 - x);

            //~ for (int i = last - y + 1; i <= last; ++i) {
                //~ curAns += a[i];
            //~ }
            // performing the same with prefix sums instead
            curAns += pref[last + 1] - pref[last - y + 1];


            curAns += a[last] * (n - last - 1);
            stratAns = min(curAns, stratAns);
        }
    }
    ans = min(ans, stratAns);
    cout << ans << endl;