765. Велосипед

Велосипедист собирается проехать из пункта A в пункт B, расстояние между которыми составляет l м. У него есть велосипед, который может развивать скорость v м/c. Однако перед тем как выехать, велосипедист может выполнить некоторые модернизации своего велосипеда. Для каждой модернизации известно на сколько она увеличивает скорость велосипеда, а также время, за которое она может быть сделана. Можно выполнить несколько различных модернизаций, однако каждая модернизация может быть выполнена не более одного раза. Помогите велосипедисту добраться до пункта B как можно быстрее.

Вход. Сначала идут три целых числа: расстояние между пунктами l (0 ≤ l ≤ 10⁹), исходная скорость велосипеда v (1 ≤ v ≤ 10⁶) и количество различных модернизаций n (0 ≤ n ≤ 100). Далее идут n пар целых чисел, каждая из которых определяет соответствующую модернизацию: прирост скорости после модернизации v_i (0 ≤ v_i ≤ 1000) и время t_i (0 ≤ t_i ≤ 1000), затрачиваемое на эту модернизацию. Все величины заданы в системе СИ (метры и секунды).

Выход. Вывести минимальное время с шестью десятичными знаками, которое потребуется велосипедисту для того чтобы доехать из пункта A в пункта B с учетом времени на модернизации.

Пример входа 1	Пример выхода 1
100 5 2 5 3 5 3	12.666667
Пример входа 2	Пример выхода 2
100 4 3 1 2 2 4 3 6	20.285714

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Пусть dp[i] хранит наименьшее время, через которое можно добиться прибавки скорости i. Изначально положим dp[i] = +∞, dp[0] = 0.

Рассмотрим пару модернизации (v_i, t) означающую что за время t можно получить прирост по скорости v_i. Рассмотрим прирост скорости j (j > 0), который можно получить за время dp[j] Тогда используя модернизацию (v_i, t), можно получить прирост скорости j + v_i за время dp[j] + t. И если это время окажется меньше dp[j + v_i], то значение dp[j + v_i] следует улучшить.

Далее ищем время, за которое можно добраться из пункта A в пункт B при условии что прирост скорости велосипедиста составит i = 0, 1, 2, … . Например, если велосипедист будет ехать со скоростью v + i, то его время поездки составит l / (v + i) + dp[i] секунд. Среди всех таких времен находим наименьшее.

Пример

Рассмотрим второй тест. Рассмотрим как изменяется состояние массива dp с обработкой очередной модернизации.

Например dp[5] = 10 означает, что прирост скорости 5 можно набрать за 10 секунд. Для этого достаточно воспользоваться второй и третьей модернизациями.

Реализация алгоритма

Объявим рабочий массив dp.

#define MAX 100010

int dp[MAX];

Читаем входные данные. Инициализируем массив dp.

scanf("%d %d %d",&l,&v,&n);

memset(dp,0x3F,sizeof(dp)); dp[0] = mx = 0;

Совершим пересчет массива dp для всех модернизаций.

for(i = 0; i < n; i++)

{

scanf("%d %d",&vi,&t);

for(j = mx; j >= 0; j--)

if (dp[j] + t < dp[j + vi]) dp[j + vi] = dp[j] + t;

mx += vi;

}

Для каждого значения прироста скорости i вычислим время, необходимое для преодоления расстояния из пункта A в пункт B. Оно равно величине пути l, деленное на скорость велосипедиста v + i, плюс время модернизации dp[i]. Наименьшее из таких времен и будет искомым.

res = 1e10;

for(i = 0; i <= mx; i++)

{

temp = 1.0 * l / (v + i) + dp[i];

if (temp < res) res = temp;

}

Выводим ответ.

printf("%.6lf\n",res);