問題概要 略解法 O(N^3)のDPは容易に思いつく． 実はmonge性を満たすため，monge-dp にできる． https://gist.github.com/asi1024/5751b073d3f422206e5a/revisions な感じで高速化．