dereference_pointer_there
#prog #puzzle
Назовём операцией заполнения присваивание всем элементам массивам в заданном поддиапазоне определённого значения. На вход подаётся массив целых чисел. За какое минимальное количество операций заполнения можно получить этот массив из массива той же длины, заполненного нулями?
Примеры:
12345
— минимальное количество операций равно 5
1212
— минимальное количество операций равно 3 (0000
-> 1111
-> 1222
-> 1212
)
Сразу скажу, я не знаю, как решить эту задачу.
Есть такая мысль: если перезаписываемый отрезок целиком лежит внутри другого отрезка одинаковых значений, то тогда за одну операцию число различных отрезков одинаковых элементов увеличивается на 2. Для достижения минимального числа операций такого рожа операций должно быть как можно больше. С другой стороны, я не уверен, что примитивныя жадная стратегия тут будет работать правильно, она может оказаться чересчур недальновидной