Реши на C++ через динамическое программирование: П...

Ниже приведён один из наиболее простых и при этом эффективных способов решить эту задачу, используя идею «скользящего окна» (two pointers). Несмотря на то, что в условии упоминается «динамическое программирование», здесь удобнее применять именно технику двух указателей (по сути, это сводится к классическому приёму с вычислением максимально возможного окна при ограничении на количество «лишних» элементов).

Идея решения

1. Считаем входные данные: $n$ — количество кубиков, $m$ — количество цветов, $k$ — максимально допустимое число удаляемых кубиков, и массив colors из $n$ чисел (цвет каждого кубика).

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

   • Пусть для цвета $c$ список таких позиций называется pos[c].
   • Все эти позиции запоминаем (например, в 0-индексации).

3. Далее для каждого цвета $c$ мы выполним следующий алгоритм «двух указателей» (скользящего окна) по вектору pos[c]:

   • Пусть этот вектор имеет длину $\ell$. Тогда мы заведём два индекса $L$ и $R$ (оба в начале указывают на 0).
   • Идём правым указателем $R$ слева направо. Для текущего подотрезка от $L$ до $R$ (внутри pos[c]) вычислим:
     • $\text{число кубиков цвета } c \text{ внутри выбранного подотрезка} = R - L + 1$.
     • Позиции этих кубиков в исходном массиве занимают диапазон от pos[c][L] до pos[c][R].
       Тогда общее количество кубиков (всех цветов) в этом диапазоне: $$\text{длина} = (\text{pos}[c][R] - \text{pos}[c][L]) + 1.$$ Из них «лишние» (не цвета $c$): $$\text{лишние} = \text{длина} - (R - L + 1) = (\text{pos}[c][R] - \text{pos}[c][L] + 1) - (R - L + 1).$$ При этом мы можем удалить не более $k$ таких лишних кубиков.
   • Если $\text{лишние} \le k$, то текущее окно допустимо, и мы можем попытаться расширить его, сдвинув $R$ на 1 вправо.
   • Если $\text{лишние} > k$, то надо сужать окно, увеличивая $L$.

4. При каждом расширении окна (когда оно допустимо) мы берём его ширину $(R-L+1)$ (это число кубиков цвета $c$ подряд после удаления «лишних») и пытаемся обновить глобальный максимум.

5. В конце выводим найденный глобальный максимум по всем цветам.

Почему это работает быстро

• Все позиции кубиков каждого цвета мы собираем один раз (сложность $O(n)$ по всему входному массиву).
• Суммарная длина всех списков pos[c] равна $n$, поскольку каждый индекс кубика попадает ровно в один список.
• Для каждого списка pos[c] мы делаем один проход двумя указателями $L$ и $R$. Каждый из них сдвигается вперёд не более $\ell$ раз, где $\ell$ — длина списка для цвета $c$.
  Следовательно, во всей программе суммарно все перемещения $L$ и $R$ по всем цветам составят $O(n)$.
• Итого общее время работы $O(n)$ (при условии, что мы перебираем только те цвета, которые реально встречаются в массиве).

Пример кода на C++

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> colors(n);
    for (int i = 0; i < n; i++) {
        cin >> colors[i];
        // Считаем, что цвета идут от 1 до m
        // Но для удобства хранения сделаем 0-индексацию
        colors[i]--;
    }

    // Массив векторов: pos[c] будет хранить все индексы i, где colors[i] = c
    vector<vector<int>> pos(m);
    // Заполним pos для каждого цвета
    for (int i = 0; i < n; i++) {
        pos[colors[i]].push_back(i);
    }

    int answer = 1;  // в худшем случае ответ минимум 1, если n>0 (или 0, если можно не удалять ничего, но тут n>=1)
    // Пройдемся по каждому цвету
    for (int c = 0; c < m; c++) {
        // Если цвет c ни разу не встречается, пропускаем
        if (pos[c].empty()) continue;

        // Два указателя по списку позиций
        int L = 0;
        // В pos[c] хранятся индексы данного цвета, уже в отсортированном виде
        // (так как мы заполняли их в порядке обхода массива)
        for (int R = 0; R < (int)pos[c].size(); R++) {
            // Проверяем, не превысили ли мы разрешенное число удаляемых кубиков
            // while &laquo;лишние&raquo; > k, сдвигаем L
            while (true) {
                // pos[c][R] - pos[c][L] + 1 — общее число кубиков в диапазоне
                // (R - L + 1) — число кубиков цвета c
                // Лишние = (общее число в диапазоне) - (число кубиков цвета c)
                int total = pos[c][R] - pos[c][L] + 1;
                int countColor = (R - L + 1);
                int notColor = total - countColor;

                if (notColor <= k) {
                    break;
                } else {
                    L++;
                }
            }
            // Здесь мы имеем максимально широкое окно [L..R], которое можно &laquo;очистить&raquo; до однородного цвета c
            answer = max(answer, R - L + 1);
        }
    }

    cout << answer << "\n";
    return 0;
}

Пояснение

• pos[c] — позиции (индексы в исходном массиве) всех кубиков цвета $c$. Они автоматически оказываются отсортированными, так как мы просто перебираем массив слева направо.
• Отрезок [L..R] по pos[c] соответствует подмножеству кубиков одного цвета, которые в исходном массиве занимают диапазон от pos[c][L] до pos[c][R].
• «Лишних» кубиков между ними (тех, что не цвета $c$) получается total - countColor, где
  • total = pos[c][R] - pos[c][L] + 1 — общее количество кубиков (всех цветов) на отрезке исходного массива от pos[c][L] до pos[c][R].
  • countColor = R - L + 1 — число кубиков именно цвета $c$ в этом же промежутке (так как мы явно знаем, что в pos[c] лежат только кубики цвета $c$).
• Если $\text{лишние} \le k$, значит мы можем удалить все эти «лишние» кубики за счёт нашего лимита $k$ и получить подряд идущую цепочку из $R-L+1$ кубиков цвета $c$.
• Перебираем все возможные варианты такого окна для каждого цвета и берём максимум.

Таким образом, решение работает за $O(n)$ при аккуратной реализации и даёт верный результат.

Важно: если $k = 0$, алгоритм тоже корректно работает, просто тогда «лишние» кубики должны быть равны нулю, чтобы расширять окно (то есть кубики цвета $c$ уже должны идти подряд в исходном массиве).

Дополнение: Если бы нам требовалось именно «полностью» выписать новую последовательность либо восстановить, какие кубики удалять, это была бы отдельная история. Но по условию достаточно вывести максимальную длину однородного фрагмента после удаления, что и делает данный код.