DP雑記④

こちらの問題を解いたのだけど、証明がまだきちんとできないことに気付いた。

証明したいのは「既に食べるピザが決まっているとき、価格の降順でソートして前から有料→無料→有料→…のように買うのが最善」という命題。交互に食べることが最善だなんてどうやって証明するのか。解説ページをすべて見たけど証明はなさそう。残念。