Тема: тимус 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

Re: тимус 1087

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

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

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

Re: тимус 1087

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

4

Re: тимус 1087

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

Anton.Hola