Может кто-нибудь объяснить мне решение DP Topcoder рандомных блин вызов в SRM656
Задача состоит в следующем: http://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416
У Чарли N блинов. Он хочет подать некоторым из них на завтрак. Мы будем нумеровать блины от 0 до N-1. Для каждого i, блин i есть ширина i+1 и вкусность d[i].
Чарли выбирает блины, которые он собирается подать, используя следующий рандомизированный процесс: он начинает с того, что выбирает первый блин равномерно наугад из всех имеющихся у него блинов. Он кладет выбранный блин на тарелку. Этот блин теперь формирует дно будущей стопки блинов. Затем Чарли повторяет следующую процедуру:
Если блинчиков больше не осталось, прекратите. Выберите блин равномерно наугад из блинов, которые еще не были выбраны. Если ширина этого блина больше ширины блина в верхней части стопки, прекратите его, не взяв. Поместите выбранный блин сверху стека и вернитесь к шагу 1. Вам дают int[] d с N элементами. Общая восхитительность порции блинов - это сумма аппетитности всех блинов, используемых в порции. Вычислите и верните ожидаемое значение общей вкусности блинов, выбранных Чарли.
Эта проблема включает в себя вероятность, и я не получаю решение DP для нее.