コードフォース-615C、主なアイディア

Question

私はコードフォース＃338、div.2の編集ページでタスク615cの説明を見つけました。私はそのアイデアを理解できません： "kコーティングを使って部分文字列t [i、j]を作ることができれば、kコーティングを使って部分文字列[i + 1、j]を作ることもできるということです。毎回最も長い部分文字列を使用する "。毎回最も長い部分文字列を使用すべきであるという文からどのように示唆されますか？それをもっとはっきりと説明できますか？ここに仕事があります：http://codeforces.com/contest/615/problem/C

Answer 1

Ayratははさみと糊を持っています。 Ayratはいくつかのコーティング（基本的には文字列）を購入し、その後、それぞれを正確に1つの連続ピース（部分文字列）から切り取り、トラックコーティングの最後まで接着します。さらに、彼はそれを接着する前にこのブロックを裏返すことを選ぶかもしれません。

substring t[i + 1, j]は、substring t[i, j]と比べて1文字少なくなります。ですからkコーティングからsubstring t[i, j]を切り取ることができれば、確かにsubstring t[i+1, j]を切り取ることができます。

は、あなたがk(=2)コーティングを使用abc + cba = abccbaを形成することができ、あなたがコーティングabcが設けられているとしましょう。

これは、（ccbaでも可）をコーティング2で形成できることを意味します。

あなただけkコーティングのいずれかから1つの余分文字（最初文字）をカットする必要があります。

代わりに、文字列に形成されたバイk -coatingsから複数の文字（複数可）を低減することが「たちは、コーティング供給のk-1または少ない数でそれを行うことができますか？」逆問題を提起すべきである

毎回最も長い部分文字列を使用する必要があります。

毎回最長の部分文字列を取得すると、問題の目標であるコーティング数が減少します。