ABC-G - Increasing K Times
メモ
問題の形からT - Permutationを連想し
dp[i][k] := i個置いたときに、前回置いた数よりも大きい数が何個残っているか
として遷移しようとしたがうまくいかなかった。
O(N^3)になってしまった
permutationの場合は、各iについて大小関係が初めから決まっているので挿入が出来なかったが、今回の場合は挿入が効果的だった。
小さい順に見ることで、大小関係の制約を解決できるのは頻出なので頭に置いておきたい
例
メモ
問題の形からT - Permutationを連想し
dp[i][k] := i個置いたときに、前回置いた数よりも大きい数が何個残っているか
として遷移しようとしたがうまくいかなかった。
O(N^3)になってしまった
permutationの場合は、各iについて大小関係が初めから決まっているので挿入が出来なかったが、今回の場合は挿入が効果的だった。
小さい順に見ることで、大小関係の制約を解決できるのは頻出なので頭に置いておきたい
例