Разделим все грузовики на классы по сумме l + r + c. Утверждается, что все входящие в ответ грузовики находятся в одном классе.
Для каждого класса решим задачу отдельно. Будем рассматривать все грузовики из одного класса в том порядке, в котором они едут, и поддерживать такую динамику: z[k] = наибольшая сумма, которую можно набрать, если у последнего взятого грузовика ri = k. Рассмотрим грузовик номер i - возможны 2 перехода:
Он может улучшить z[ri] значением z[ri + ci] + vi, т. е. продолжить уже начатую колонну машин, в которой r у последнего грузовика равно ri + ci. (Для соседних в колонне грузовиков должно выполняться: rprev = ri + ci )
Если li = 0, он может улучшить z[ri] значением vi, т. е. стать первым в новой колонне машин. (Для первого в колонне грузовика должно выполняться: li = 0)
Ответ на задачу будет записан в z[0].
Для восстановления вошедших в ответ грузовиков, вместе с наибольшей суммой в z можно хранить номер последнего грузовика, улучшившего эту сумму. Еще мы отдельно храним предка p для каждого грузовика, улучшившего хоть что-то в z. Этот предок считается один раз когда мы рассматриваем i-ый грузовик и больше не изменяется: p[i] = -1 если грузовик i стал новым началом колонны, иначе p[i] = последний грузовик, улучшивший z[ri + ci].
Начинать восстановление ответа нужно с последнего грузовика, улучшившего z[0]. Дальше все восстанавливается только по p.
Не могли бы вы поподробнее описать процесс восстановления ответа? Пусть у нас есть такой тест:
3
1 1 0 1
1 1 1 0
2 1 0 1
Значение ответа получится верное - 2. Но при восстановлении, когда мы придем в z[1], там будет записано 2 и что мы пришли туда по 3-му грузовику, т. е. окончательный ответ получится
2
3 2
что неверно, т. к. противоречит условию, что грузовики нельзя переставлять в колонне местами.
PS The task with "at least" is also solvable with the same limits on input data.