Олимпиадная задача про стратегию набора фишек в казино для 8–11 классов (сложность 5/5)

Тесты и проверяющая программа Решения, написанные членами научного комитета и жюри Всероссийской олимпиадыРазбор задачи "Казино" Заметим, во-первых, что не любая стратегия игрока приводит к нужному результату. Например, если в примере, разбиравшемся в условии задачи (rrrgggbbb и т.д.), стоимость буквы b будет больше стоимости буквы r, то только один из путей приводит к оптимальному результату: три раза забрать буквы gb. После некоторого размышления можно понять, что всевозможные т.н. "жадные" решения - делать самый выгодный ход, делать самый длинный ход, делать самый левый ход, и т.п. - также в большинстве случаев неверны. Перебирать же все варианты, для каждого из них - опять все варианты, и так далее - оказывается слишком медленным подходом.Для решения этой задачи применим динамическое программирование. В первой половине решения мы для каждого куска начальной последовательности фишек определим, можем ли мы забрать его целиком, не затрагивая при этом остальные фишки. Иными словами, для всех l и r найдем величину a[l,r], равную 1, если фишки с номерами (то есть позициями в начальном расположении, считая слева) с l по r игрок может за несколько действий все забрать себе, и 0 - в противном случае. Затем по этим данным во второй половине решения мы восстановим ответ к задаче.Во избежание путаницы будем называть последовательности, объявленные крупье (в отличие от начальной последовательности) словами.Вторая половина решения проще первой, поэтому начнём с неё. Пусть нам известны величины a[l,r]. Пусть тогда b[l,r] - это максимальная сумма денег, которую можно получить, играя только на отрезке с l-ой фишки по r-ую (то есть, не трогая остальных фишек). Ясно, что если a[l,r]=1, то b[l,r] - это просто сумма стоимостей всех фишек с l-ой по r-ую. Если же a[l,r]=0, то уже не удастся забрать все фишки, соответственно, какая-то из фишек должна остаться - пусть это фишка с номером k. Тогда заметим, что задача распадается на две - для фишек слева от k-ой и для фишек справа от неё, т.е. что b[l,r]=b[l,k-1]+b[k+1,r] (здесь и далее мы считаем, что для любого m b[m,m-1]=0). Но так как номер оставшейся фишки не фиксирован, то в действительности b[l,r] равно максимуму этих величин по всем k:()(напомним, что эта формула верна при a[l,r]=0). Теперь мы видим, что для нахождения величин b[l,r] можно применить динамическое программирование: если мы будем перебирать r от 1 до длины начальной последовательности, а затем l от r до 1, то к моменту вычисления величины b[l,r] все величины, которые необходимы для её нахождения по формуле (), уже вычислены. Таким образом, зная величины a[l,r] мы можем найти b[l,r]. Легко видеть, что на этом шаге требуется порядка L³ действий (напомним, что L - это длина начальной последовательности).Теперь вернёмся к первой половине решения, а именно - нахождению величин a[l,r]. Как узнать, можно ли забрать себе данную последовательность (в нашем случае - кусок начальной) целиком? Во-первых, возможно, эту последовательность можно разделить на две части, каждую из которых можно забрать себе целиком. То есть, если найдётся k такое, что a[l,k]=1 и a[k+1,r]=1, то и a[l,r]=1. Если же так сделать не удаётся, то можно заметить, что если мы всё-таки заберём всю последовательность целиком, то её первую и последнюю фишки мы заберём только на последнем шаге. Пусть на последнем шаге мы заберём некоторое слово S. Тогда задача сводится к тому, чтобы выкинуть из последовательности некоторые куски (можно считать, что для этих кусков величина a уже посчитана, поэтому мы знаем, какие из них можно выкинуть, а какие - нет), оставив первую и последнюю фишки на месте, так, чтобы осталось слово S. Для решения этой задачи опять применим динамическое программирование. А именно, пусть c[l,r,p,q]=1, если можно из отрезка с l-ой фишки по r-ю можно так выкинуть несколько кусков, чтобы остались первые q фишек слова номер p, и при этом l-я и r-я фишки остались на месте, и 0 - иначе (тогда нас интересует величина c[l,r,p, length(p)], где length(p) - длина слова номер p). Во-первых, ясно, что если первая фишка слова номер p не совпадает с l-ой фишкой начальной последовательности, или q-я - с r-ой, то c[l,r,p,q]=0. В противном случае, пусть (q-1)-я фишка слова получится из k-ой фишки последовательности. Тогда, во-первых, должно быть c[l,k,p,q-1]=1 (чтобы получить первые q-1 фишек), а, во-вторых, a[k+1,r-1]=1 (чтобы выкинуть кусок между (q-1)-й фишкой и q-й). Но так как число k не фиксировано, то получаем, что c[l,r,p,q]=1 тогда и только тогда, когда найдётся такое k. Тем самым получен алгоритм для подсчета c. Оценим время его работы. На подсчёт одного элемента массива c требуется порядка L действий (по количеству возможных k). Нам необходимо подсчитать элементы вида c[l,r,p,length(p)]. Из вышеприведённых рассуждений легко заметить, что для их подсчёта нам потребуется подсчёт только элементов вида c[l,...,...,...], а элементов такого вида порядка L∙S (где S - сумма длин всех слов), так как для параметра r есть порядка L вариантов, а для пары параметров (p,q) - порядка S вариантов. Тем самым мы для любых l и r можем найти a[l,r] за порядка L∙L∙S= L²∙S действий, а общее время работы получается порядка L²∙L²∙S=L⁴∙S.Однако легко заметить, что если подсчитать все величины c[l,r,p,q] сначала, а потом лишь использовать найденные значения, то время работы будет меньше. Действительно, всего в массиве c L²∙S элементов, и на подсчёт каждого из них уйдёт порядка L действий, тем самым общее время работы будет порядка L³∙S. Также доступны документы в формате DOC

Ответ задачи отсутствует