[AOJ] No. 0340 パンケーキ

問題

方針

両端のパンケーキは \( 1 \) 枚だけ裏返すことができることに着目します。左端のパンケーキは単独で裏返す回数を \( k \) とすると、最小値を達成するためには、\( 0 \leq k \leq p_1 \) であることが分かります。ここで、\( k \) 回左端のパンケーキを単独で裏返した場合、\( p_1 \leftarrow p_1 – k \) と値を更新します。次に、\( 2 \) 枚同時に裏返すので、パンケーキの裏返す回数は、\( 2p_1 \) 増加し、\( p_2 = \max(0, p_2 – p_1) \) となります。次に、左から \( 2 \) 個目のパンケーキと \( 3 \) 個目のパンケーキを裏返すので、\( 2p_2 \) となり、\( p_3 = \max(0, p_3 – p_2) \) となります。この操作を \( N – 1 \) まで繰り返し、\( p_N \) 回単独で右端のパンケーキを裏返すことになります。

コード

感想

解説を見てまさか全探索だとは思いませんでした。