Это был мой 3-ий SRM.
Прерыдущие 2 были слиты и я находился на 521 месте в своём дивизионе.
В этот раз участников было более 2000, и мне казалось, что сейчас я продолжу своё падение.
Но взяв себя в руки сел его писать.
Первая задача сдалась быстро.
Вторая же показалась весьма интересной.
Написав первое придуманное решение и проверив его на демо тестах, я его отослал.
Но уже тогда во мне закралось ощущение, что решение уж больно короткое получилось и в принципе могло чудом пройти демо тесты, но просто обязано свалиться на System Test.
Не придумав ничего путного по 3 задаче до конца соревнования пытался понять своё решение, но так и не понял.
Каково же было моё удивление, когда обе задачи прошли System Test и я с 521 места переместился на 38, получив +221 рейтинга.
Просмотрев решения всех, кто выше меня по рейтингу я был удивлён, что ни у кого не было линейного как по памяти так и по количеству действий, однопроходного решения.
Я уже перестал верить в чудеса и то, что ко мне приходит озарение и "заходит" вообще непонятно каким образом моё решение.
В общем у меня вопрос - может ли кто нить объяснить - почему моё решение зашло. Это weak tests или на несколько минут в меня вселился дух какого то профи и при этом свалил тут же после отправки этого решения, не объяснив его корректность.
Ты будешь смеяться - но я никоим образом не старался написать какое то хитрое решение,т.к ДП я не всегда даже более простое придумываю. Вот это всё как раз и удивляет. Поэтому определенно хотелось бы узнать "нормальное" решение по этой задаче, ну и почему мой код зашёл )
http://www.topcoder.com/stat?c=problem_solution&rm=306316&rd=14240&pm=11157&cr=22840202
У тебя в решении тоже ДП, только вместо конечного результата у тебя хранится его изменение.
0, k+1, 2k+2 ...
1, k+2, 2k+3 ...
...
k, 2k+1, 3k+2 ...
Для каждого набора таких чисел посчитаем следующее ДП:
в dp[i] будем хранить максимальную сумму включенных чисел. Переходы следующие:
1) Мы можем включить числа i, i+1 в отрезок. Тогда сумма, которую мы получим будет: dp[i-1]+p[i]+p[i+1]. (dp[i-1], потому что каждое число мы можем включить макс. в 1 отрезок)
2) Мы можем пропустить число i+1 (не включать в отрезок с i). Тогда мы получим сумму просто dp[i].
Из этих 2-х переходов выберем максимальный: dp[i+1]=max(dp[i-1]+p[i]+p[i+1],dp[i])
Можно не разбивать на наборы в явном виде.
В твоем случае: в res[i] хранится изменение итогового результата, если мы возьмем числа i, i-k-1. Тут действие одно:
1) Мы берем числа i, i-k-1. Тогда нужно отнять изменение, если мы взяли числа i-k-1, i-2k-2. Т.е. результат dp[i]-dp[i-k-1].
Если лучше взять числа i, i-k-1 а не числа i-k-1, i-2k-2, то результат будет положительный. И мы добавим его к сумме. Если же нет, то ничего добавлять не надо.
P.S. Чем-то похожая задача:
http://olympiads.ru/sng/2/description2.shtml
Кстати приезжайте к нам на itfest, а то чего-то совсем в последнее время притихли