• Зарегистрирован: 2009-06-21
  • Сообщений: 28

Тема: тимус 1087

http://acm.timus.ru/problem.aspx?space=1&num=1087
В чем ошибка моего решения?

m[k] - по сколько можно брать
dp[ i ] - показывает выйгрышна, проигрышна или пока неизвестно про кучу с  i камнями.
dp[0] - выйгрышна

для каждого m[k]
двигаемся по dp слева на право счетчиком i :
если dp[ i ] - проигрышна, то dp[i + m[k]] - выйгрышна
елси dp[ i ] - выйгрышна,
         то  если про dp[i + m[k]] неизвестно или она проигрышная,
                         то dp[i + m[k]] - проигрышная,
         иначе ( dp[i + m[k]] - была выйгрышной )
                 dp[i + m[k]] - выйшрышная
затем смотрим на dp[n] и делаем вывод, если выйгрышная то первый выйграл, иначе второй выйграл.

2 Ответ от denton

  • denton
  • Участник
  • Неактивен
  • Откуда: Санкт-Петербург
  • Зарегистрирован: 2009-07-05
  • Сообщений: 13

Re: тимус 1087

Мне кажется, два цикла следует поменять местами:

двигаемся по dp слева направо счётчиком i :
для каждого m[k] :
...

, потому что в твоём варианте рассматривая кучку i и собираясь выкинуть m[k], ты ещё не можешь быть уверен, что для кучки i у тебя уже посчитан наилучший ответ (поскольку в будущем мы можем обновить ответ для этой кучки, рассматривая другое m[k]), следовательно и переходы из состояния, в котором ответ ещё не посчитан, не имеют смысла

  • Зарегистрирован: 2009-06-21
  • Сообщений: 28

Re: тимус 1087

Точно же! Спасибо)

4 Ответ от Anton

  • Anton
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-12-20
  • Сообщений: 4

Re: тимус 1087

Zayakin_Andrey, привет.
Не совсем понимаю логику переходов между состояними ...
Если dp[ X ] - проигрышная (или не оцененная), то основываясь на чем, мы делаем вывод, что dp[ X + m[ k ] ] - выигрышная ?
И если dp[ X ] - выигрышная, то какова тут цепочка рассуждений ?
Хочу понять этот принцип, он много где встречается. Объяни, пожалуйста

Anton.Hola