Задача B. Рейтинг студента

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Многие вузы переходят на рейтинговую систему оценки: оценки студентов зависят от того, как они сдают задания в течение всего семестра. Для каждого задания устанавливается срок сдачи, позже которого задание не принимается.

Один студент получил N заданий утром дня с номером 1.

Студент хочет, чтобы его рейтинг стал как можно выше. Напишите программу, которая, получив информацию о заданиях, определит, какие задания и в каком порядке должен выполнять студент, чтобы максимально повысить свой рейтинг.

Рекомендуется рассмотреть частичные решения

Формат входного файла

Входной файл содержит целое число N, за которым следует N троек целых чисел Li Di Ri — информация о заданиях.

Формат выходного файла

Программа должна вывести в выходной файл максимальное количество баллов, которое может заработать студент, а затем — описания заданий, которые ему нужно для этого выполнить. Каждое описание состоит из чисел ki si — порядкового номера задания и номера дня, когда студенту нужно начать его выполнение. Все ki должны быть различны. Задания должны быть выведены в порядке возрастания si.

Если студент не сможет заработать ни одного балла, вывести единственное число 0.

Если существует несколько способов заработать максимальное количество баллов, вывести любой из них.

Ограничения

1 ≤ N ≤ 1000; 1 ≤ Li, Di, Ri ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
7 8 6
2 2 1
5 8 4
3 9 3
2 5 1
7
3 1
4 6

Разбор

Заметим, что если студент уже выбрал, какие задания он будет выполнять, то он может выполнять их в порядке возрастания Di. Такой порядок является оптимальным в том смысле, что при замене любого другого порядка выполнения заданий на этот порядок ситуация не ухудшится: если при другом порядке студент укладывался в сроки, то при таком порядке он тем более уложится в сроки. Следовательно, будем искать решение в таком виде: пусть студент выполняет задания в порядке возрастания Di.

Применим метод динамического программирования. Предварительно упорядочим задания по возрастанию Di. Подзадача с параметрами (i, j): пусть студент выполнил какие-то задания из заданий с 1-го по i-е и потратил на выполнение заданий j дней. Пусть c(i, j) — решение подзадачи с параметрами (i, j). Для вывода рекуррентного соотношения заметим, что студент мог либо выполнить i-е задание, либо нет.

Рекуррентное соотношение: c(i, j) = max(c(i − 1, j), c(i − 1, j − Li) + Ri).


0.098s 0.009s 13