Добрый вечер.
В этом посте я разберу задачу B «Дубы» с практического тура городской олимпиады школьников Санкт-Петербурга по информатике.
Задача эта на динамическое программирование по подотрезкам и идея решения интересна тем, что удобнее посчитать две динамики вместо одной. Если вас заинтересовало (незнание динамики не освобождает, но будет труднее) — добро пожаловать.

Вместо КДПВ — короткая драма для привлечения внимания, основанная на реальных событиях. Ее можно смело пропустить и перейти к статье, которая поможет вам разобраться в rvalue-ссылках, конструкторах перемещения, универсальных ссылках, идеальной передаче (perfect forwarding) и т. д.

Драма в трех действиях

Действие первое

Компилятор. Локальный объект x типа T, проживающий на стеке, вы приговариваетесь к изъятию у вас всего имущества в связи с тем, что не будете пользоваться им до конца своей жизни.

Объект x. Что? Я не какой-то там временный объект, у меня постоянная регистрация, вы не имеете права!

Компилятор. Никто вас не выселяет. Но согласно одиннадцатой редакции стандартного кодекса, все ваши вещи будут переданы другому объекту, которому они нужны больше.

Объект x. И как вы это сделаете? Все мои данные надежно инкапсулированы, я не позволю никому бесцеремонно обращаться с ними. Если уж они так вам нужны, то пусть приходит конструктор копирования со своей флешкой, я ему скопирую.