спасибо)

сам написал, и когда штраф = 1, то не работает, а когда 2 — все отлично. С чем это связано?

Приношу извинение за долгий ответ.

Первый нюанс состоит в том, что для применения лямбда-оптимизации требуется важное свойство — от добавления каждого нового отрезка ответ должен улучшаться меньше, чем от добавления предыдущего (или на крайний случай — улучшаться точно так же). Однако для исходной задачи это свойство не выполняется. Рассмотрим пример 000011100. При $$$k=1$$$ у нас будет три несоответствия, при $$$k=2$$$ — два несоответствия, т.е. ответ улучшился всего на $$$+1$$$, а при $$$k=3$$$ — ноль несоответствий, т.е. ответ улучшился уже на $$$+2$$$. Из-за этого у нас не будет такого значения штрафа, при котором мы бы из всех вариантов предпочли выбрать два отрезка, всегда мы будем предпочитать брать или один отрезок, или сразу перескакивать на три отрезка.

Задача начинает обладать этим свойством, только если мы зафиксируем четность количества взятых отрезков. Доказывать строго я это не умею, но добавление сразу двух новых отрезков позволяет, например, локально взять в предыдущем разбиении какой-нибудь одноцветный отрезок, внутри которого есть несоответствия, и превратить его в три, не затронув больше ничего остального. Тогда как добавление только одного отрезка требует кардинальным образом перестроить все разбиение, порой даже ухудшая из-за этого ответ (например, для примера 00100 при $$$k=1$$$ будет одно несоответствие, а при $$$k=2$$$ уже два). Когда я это осознал, самым безболезненным способом переделать уже написанный код стало отдельно перебрать и зафиксировать все варианты цветов первого и последнего отрезка. Тогда, если они одноцветные, отрезков обязательно будет нечетно, а если разноцветные — четно.

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