1404

携帯電話のボタンの数と割り当てるキーの種類が与えられ、それぞれのキーが何回くらい入力されるかの頻度が与えられるので、最適キー配置を答えよ、という問題。

連続する任意のキー群を一つのボタンに割り当てたときのコストを事前に計算しておいて、全体としての最小コストをDPで求めるだけ。同点の場合の処理を適当に挿入しておく。