読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2312 魔法少女さやかちゃん

AOJ

多分勉強会の問題の中で開いてから解くまでが最速だった.(これは罠で,日本語の問題だからという説がある

解法

輪というのが考えにくいのでなんとか区間というか数を一列に並べる問題にならないか考えてみます.
試しにK_{min},K_{max}の位置を固定してみると,K_{min},K_{max}の間に二本の数列が存在していることが分かります(長さ0の数列もありうる)
この二つの数列について,Kの値をどちらの数列に割り振るか決めたとき,どちらの数列も単調増加になるように並べると最適になることがわかります.
単調増加な数列を2本作ればよいので,Kの値を事前にソートしておいてDPをします.
dp(i,k):=片方の数列の最後尾がiでもう片方の最後尾がkであるときに必要な精神力の和の最小値
とすると各状態の遷移は累積和を使えばO(1)でできるのでO(N^2)でできます.
空間計算量もdpの配列を使いまわしていけばO(N+M)になります.