まあケースあたりO(N^2)くらいのDPをするだけ。 ケースがたくさんあるから最初に全部前計算をtotal O(N^3)未満でやるのかなと思ったら、ケース数が全然なかった。(このせいで無駄に時間を消費した) テストケース数に強く依存する計算量の問題はケース数とか…