ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2312 - 魔法少女さやかちゃん

動的計画法(DP) Binary Indexed Tree(BIT)

問題
 提出コード

解法

添え字は0-indexedとします。区間の総和は、BITや累積和を用いて高速に取得できるものとします。
$P_{l,r} = \frac{\sum_{i = l}^{r}S_{i}}{L}$
とします。
仮に円環でなく直線上に音符を配置しているとした場合、明らかに音符を $K_{i}$ の昇順に配置するのが最適です。
しかし今回は、音符を並べて円環を作成しています。この場合、
$(K_{i}の最小値)...(その他の音符)... (K_{i}の最大値 )...(その他の音符)...(K_{i}の最小値)$
となっているはずです。
つまり、円環を2つに分け、二本の直線とみなすと、それぞれが広義単調増加(減少)になっていればよいことがわかります。
あとは、 $K_{i}$ を昇順でソートし、二本の直線のうちどちらに配置するか、ということを考えればいいことになります。ということで、以下のようなDPを考えます。

$dp[i][j] =$ 片方の右端が $i$ 、もう片方の右端が $j$ になっているときの最小コスト(ただし、 $i = j = 0$ もしくは $i \gt j$ )

初期値は $dp[0][0] = 0$ です。 $dp[i][j]$ の遷移は、場合分けで表されます。

$i \neq j-1$ の場合
この場合、 $i-1$ と同じ直線に $i$ を配置することになります。よって、
$dp[i][j] = dp[i-1][j] + P_{i-1,i}$
となります。
$i = j-1$ の場合
この場合、 $i-1$ を配置した直線とは違う直線に $i$ を配置します。
つまり、 $i$ と隣接する音符は、 $[0,i-1]$ のいずれか( $i-1$ は $i-1 = 0$ のときのみ可能性が存在します)であるため、
$dp[i][j] = min(dp[i-1][x] + P_{x,i})$ (ただし $0 \leqq x \leqq i-1$ )
となります。

これを計算すると、 $min(dp[n-1][i] + P_{i,n-1})$ が答えになります。