Вот условие задачи. Начальные значения:
F[0][0]=100;
F[0][1]=F[0][0]/Price[0][0]; // макс. количество долларов в нулевой день
F[0][2]=F[0][0]/Price[0][1]; // макс. количество евро в нулевой день
//Переходы
for(int i=1; i<n; i++)
{
F[i][0]=max(max(F[i-1][1]*Price[i][0], F[i-1][2]*Price[i][1]), F[i-1][0]);
F[i][1]=max(F[i-1][0]/Price[i][0], F[i-1][1]);
F[i][2]=max(F[i-1][0]/Price[i][1], F[i-1][2]);
}
// Ответ в F[n-1][0]
Суть такова, что в F[i][0] лежит максимальное кол-во рублей, которое можно собрать в первые i дней. Price[i][0] — курс доллара в i-тый день. Price[i][1] — курс евро в i-тый день.
Над задачей ломаю голову вторые сутки. Симпл тест проходит, прога падает с WA2. Если динамика верна, то буду искать в коде ошибку, иначе прошу подсказки.
Спасибо!
P.S. А те, кто ставят минусы, они вообще пытались помочь? Чем обосновываются эти минусы?
P.P.S. Это исправленная версия, после замечания dima_gozha, которая также падает с WA2.
P.P.P.S. Задача решена, отдельное спасибо KADR!
Динамика не совсем верна. Вы не учли ситуация когда выгодна купить валюту в первый день, а продать в последний!!
Я в первый день покупаю валюту, которая более выгодна, во второй продаю более выгодно. Потом опять же покупаю более выгодно и так далее. Взможно, я не учел, что не обязательно продавать или покупать в какой-то день?
На тесте 3 1 1 3 3 10 10 Ваш ответ 333.3 а надо 1000.0
Спасибо за помощь!
Решил эту проблему взятием максимума между текущим и предыдущим днем по рублям, долларам и евро. Ответ на данный тест верен теперь. Но тот же WA2.
Если не учитывать очевидного бага в 3-й строке, то динамика не рассматривает случай, когда нам выгодно сделать несколько обменов в один день. Например, в первый день курсы 1 и 100, во второй день курсы 100 и 1, а в третий — 1 и 100. Тогда в первый день нам выгодно купить 100 долларов, во второй — продать доллары и купить евро, а в третий — продать евро.
Фрагменты кода я писал не с компьютера, от туда и баг. Спасибо большое за помощь! Сейчас перепишу динамику.
Я вообще не понимаю, почему тебя минусуют.
Ура, зашла! Спасибо тебе оромное!
А что за баг в 3-й строке ???
Его уже исправили :) Раньше там было Price[0][0] вместо Price[0][1].