PAST006N DPをしたいが,順序によって得られる値が変わる. よって,最適な順序にソートしてからDPする.\(i \rightarrow j\) , \(j \rightarrow i\) のそれぞれに対して得点を調べて, 差分を計算すれば \( a_{i}/ b_{i} \geq a_{j} / b_{j}\) の順で行うのが最善と分かる. これは直観にも合致する. 気持ちとしては \(a_{i}\) を大きい順に, \(b_{i}\) は小さい順に行いたいから. 最適順でソートしてからDPというのは, 一般的な話として使える. 例えば,食塩水のDPも最適順にソートしている. また,順…