大分・・・

プログラム PKU

DP(動的計画法)のコツが分かってきた。
より小さいサイズの場合の最適解を適切に求めて置いて、ソレをより大きいサイズの問題の解の一部として利用する。

  • 2030 - The Secret Number

DPの典型例。図上だと、右下から順にその場での最適解を求めていく。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2030


最初はlist+mergeでやろうと思ったけど、mergeでは特定条件下でソートがかかるみたい。後ろに挿入してくれるだけでいいのに。
結局、各マスを表す構造体を作ってクリア。