[Codeforces] Educational Codeforces Round 59 C. Brutality

Brutality

https://codeforces.com/contest/1107/problem/C

考え方

題意

‘a’ – ‘z’ までの26個のボタンがあり、数字の配列 \( a \) と文字列 s が与えられます。\( a \) と s のインデックスは対応していて、s の \( i \) 番目の文字を \( x_i \) とすると、\( x_i \) を押すと、\( a_i \) の点数が加算されます。ただし、同じボタンの文字は連続して \( k \) 回しか押すことはできません。また、ボタンを押さないことも許されます。例えば、ボタンを押さなかった場合を〇とすると、aa〇a とボタンを押したときは、a を三回連続で押したことになります。

このときの点数の最大値を求めます。

方針

連続する文字に対応する \( a_i \) のリストを作成し、リストを降順に並び替え、上から \( k \) 個選べば良いです。

コード

感想

コンテスト中に題意を理解することはできませんでした。解説を読んで問題文の意味が分かりました。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする