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

Question

Дано целое число k и отсортированная гистограмма с n столбцами с высотой a1, a2, a3,..., an (эта последовательность не уменьшается, поскольку гистограмма отсортирована). Мы должны выбрать k столбцов (1 <= k <= n) из этих n столбцов, чтобы область, заключенная между выбранными столбцами и правой стенкой гистограммы, была минимально возможной.

Например, для последовательности высот {1, 3, 5, 9}, если мы выбрали столбцы с высотами 1, 5; площадь, окруженная правой стеной, будет 12 единиц и будет выглядеть примерно так, как показано на рисунке (допустим, что ширина столбцов равна 1 единице.)

Попробовав несколько жадных подходов (которые были неверны), я перешел к следующему решению динамического программирования:

Определите dp[i][j][last] как минимальную область при выборе j баров из первых i баров из гистограммы так, чтобы предыдущий бар, который мы взяли направо, имел индекс last.

dp[i][j][last] = min(dp[i - 1][j][last], dp[i - 1][j - 1][i] + a[i] * (last - i));

Но проблема в том, что он слишком медленный, его O (n ² k) , поэтому я надеюсь, что кто-нибудь поможет мне оптимизировать его до чего-то вроде O (нк) или, может быть, предложить более быстрое жадное решение.

Answer 1

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

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

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

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

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;

Answer 2

В дальнейшем я собираюсь предположить, что 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) `.