Codeforces -615C, основная идея

Question

Я столкнулся с объяснением задачи 615c на редакционной странице codeforces # 338, div.2. я не могу понять идею: «Идея состоит в том, что если можно сделать подстроку t [i, j], используя k покрытий, то мы также можем сделать подстроку t [i + 1, j], используя k покрытий. используйте самую длинную подстроку каждый раз ». Как можно заключить из этих предложений, что мы должны использовать самые длинные подстроки каждый раз? не могли бы вы объяснить это более четко? Вот задача: http://codeforces.com/contest/615/problem/C

Answer 1

Айрат имеет ножницы и клей. Айрат собирается купить некоторые покрытия (в основном это струны), а затем вырезать из каждого из них ровно одну непрерывную деталь (подстроку) и приклеить ее до конца покрытия его дорожки. Более того, он может перевернуть этот блок перед тем, как приклеить его.

substring t[i + 1, j] содержит ровно 1 знак меньше по сравнению с substring t[i, j]. Так что, если вы можете вырезать substring t[i, j] от k покрытий, то вы можете наверняка вырезать substring t[i+1, j].

Допустим, вы снабжены покрытием abc, то вы можете сформировать abc + cba = abccba использованием k(=2) покрытий.

Это также означает, что вы можете сформировать bccba (даже ccba) используя 2 покрытие.

Вам просто нужно вырезать один дополнительный характер (первого символов) из любого одного из k покрытий.

Вместо сокращение больше символа (ы) из строки сформированных в каждом конкретном k -coatings должны поднять обратный вопрос «Могут ли мы сделать это в k-1 или меньшем количестве поставок лакокрасочных?»

Таким образом, мы должны использовать длинные подстроки каждый раз

Когда вы дольше подстроки каждый раз, количество покрытий уменьшается, что и является целью данной проблемы.