halin.george's blog

By halin.george, 11 years ago, In Russian

Вот условие задачи. Начальные значения:

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!

  • Vote: I like it
  • +1
  • Vote: I do not like it