[AOJ] No. 0644 水ようかん (Mizuyokan)

2019年11月11日

問題

方針

最小値を固定

水ようかんを切り分けた時の長さの値は、切る箇所を任意の \( 2 \) 点選ぶことを考えると、最大でも

\[\dfrac{N(N + 1)}{2} – 1\]

あることが分かります。したがって、最小値を固定したときの、最大値を変数とみて、最大値の最小値を求めます。

動的計画法

水ようかんのピースの最小値を \( l \) と固定して動的計画法を行います。このとき、\( d_i \) を \( i \) 番目の切れ目まで調べたのピースの最大値の最小値とします。初期値は、\( d_i = 0 \) とし、それ以外は、\( d_i = \infty \) とします。また、更新後の配列は \( l \leq d_i \ ( i \neq 0 )\) を満たす必要があります。

配列の更新は、\( i \) 番目の切れ目から先頭に向かって連結させていきます。このときのピースの長さを \( t \) とします。\( 0 \leq j \leq i \) となる \( j \) について、\( l \leq t \) のとき、

\[d_{i + 1} = \min(d_{i+1}, \max(d_j, t))\]

となります。\( j \) について、\( i \) から \( 0 \) へと更新していきます。

コード