Educational DP Contest / DP まとめコンテスト N - Slimes
解法
とします。
体のスライムを合体していくのではなく、
体の大きさ
のスライムを、
体に分解していく、というようにして考えていきます。
このとき、大きさのスライムを分解するときのコストは
になります。
区間
のスライムが1体になっているとき、それらをすべて1体ずつにバラすために必要な最小コスト
とすると、答えはになります。また、初期条件は
です。1体になった時点で、これ以上分ける必要が無いからです。
さて、1体のスライムをどのようにわけるとしても、必ずのコストは必要になるので足す必要があります(ここで、
は、
の区間の
の総和を
を用いて表した式になります)。
あとは、どこでスライムを分断するか、です。
と
とわけるとした場合、最終的な遷移は次のようになります。
ただし、です。
あとはこれをもとにして計算していけば答えを求めることができます。
感想
区間DPを、初めて再帰を使わずに書きました。が、再帰をした方がわかりやすいと個人的には思います。理由としては、引数に区間の端の情報をはっきりと書いているので、上のように式に表した時わかりやすいからです。今回自分の書いたコードは、区間の左端と、区間の幅をfor文の変数にしたため、ごちゃごちゃしています。今回のDPは、ここからさらに分断する変数(上でいうk)も必要になるので、書くのに時間がかかりました。
思考の推移としては以下の感じです。
制約をまず見たときに、が間に合いそうなので、
の添え字は3つか、2つで1つの要素を確定させるために
かけるかのどちらかだ、という目星を付けます。すると、操作の前後でスライムの順番が変わらないので、区間に対しての最善手を求めるとうまくいきそう、ということがわかり、区間DPを思いつきます。あとは、ある区間に対する最善手を考えたときに、まとめるのではなく分割していけば、わかりやすいDPがかけそう！となり、上の式を考えて、考察完了です。
