M個(M<=40)の自然数の列が与えられる。
これはSpidermanのトレーニングメニューである。
各数字は、その高さの分だけ、ビルを登るか、降りるかしなくてはいけない事を意味している。
Spidermanは地面からトレーニングを始め、終了時に地面に到着しなくてはならない。
当然途中、地下に潜る事は出来ない。
実はSpidermanは高い所が苦手な為、途中経過する最も高い点を出来る限り低くしたい。
そのような、登る/降りるの選択順序を答えよ。
不可能な場合はIMPOSSIBLEと出力。
M個の自然数の和は、1000以下。

地面に戻れるかどうかはPARTITION問題(NP完全)だとすぐに気づかなくてはならない。
解の範囲が制限されているPARTITION問題は、DPで解くのが定石。
21x1001の配列を用意する。
この配列の添え字[A][B]に、A回目の昇降が終わった時高さBに到達することが出来るかどうかと、そこに到達する為に通過しなくてはいけない最高高度の最低値、それを達成する為の選択(昇/降)を記録しておく。
後は、[0][0]を(true, 0, ?)を始めの状態として、[1][B]を全て埋める、[2][B]を全て埋める...としていけば、答えが求まるはずだ。

3003.cpp