Задача водопроводчика:
Предположим, что водопроводчик получил наряд на уста-
установку перекрытий (шлюзовых затворов) на нескольких трубах,
проложенных под землей, покрытой тяжелыми квадратными
плитами. Он может установить механизмы перекрытия в любом месте трубы, но, разумеется, лишь по одному шлюзовому затвору на каждой трубе. Для минимизации трудозатрат водопроводчику надо определить минимальное число плит, которые требуется приподнять, чтобы установить по одному
затвору на каждой трубе.