В F важно понимать, что если мы зафиксировали набор типов граблей, наступанию на которые мы не будем обучаться, то дальше нет разницы, через какие из ных мы перепрыгнем. Значит, заведем динамику f(i, j) — минимальное количество ударов по голове, если мы уже прошли первые i типов граблей и перепрыгнули j раз. Тогда мы либо обучаемся граблям текущего типа, получив a_i ударов, при этом ничего не перепрыгиваем, либо же ничему не обучаемся и перепрыгиваем по максимуму, т.е. min(K - j, b_i) раз. Сложность O(NK).

Динамика:

d[i][j], где i -- количество обработанных типов граблей, j -- количество совершенных прыжков Петей.

Для каждого состояния три перехода:

1. Мы не тратим прыжки: d[i + 1][j] = min(d[i + 1][j], d[i][j] + a[i])
2. Если хватает, мы тратим необходимое количество прыжков и не получаем: d[i + 1][j + b[i]] = min(d[i + 1][j + b[i]], d[i][j])
3. Если не хватает, тратим все оставшиемся прыжки: d[i + 1][k] = min(d[i + 1][k], d[i][j] + b[i] - (k - j))

Итого: O(NK), исходник: http://pastie.org/5669554

если прямоугольник AxB можно замостить карточками WxH,

Еще раз для тех кто в танке. Как это делать?

там можно было проще. пользуясь той фишкой с сазанки, что возможное разбиение можно поделить на две части, перебираем a и b — две части одной стороны. дальше нужно узнать c и d (a*c — прямоугольник со всеми вертикальными, b*d — горизонтальными карточками), а это просто два уравнения ac+bd=n, cw=dh. выражаем d и c отсюда целочисленно, проверяем равенства, обновляем ответ.

У меня была проблема с пониманием условия: я не понял, что нам необязательно проверять всех больных из палаты. Т.е. если k = n, то ответ может быть довольно большим.

А дальше очевидная кубическая динамика по дереву: сколько максимум из поддерева можно позвать людей, если осталось сколько-то комнат. При пересчёте "обрезаем" это количество по мощности ребра.