enakai00 https://blog.hatena.ne.jp/enakai00/ めもめも https://enakai00.hatenablog.com/ 何の話かと言うと atcoder.jp上記の問題について、AVL 木（ソート済みのリストに対して、ソートを保った挿入・削除を で実行できるデータ構造）を用いた別解を紹介します。 再帰処理による解法 まずは直感的にわかりやすい再帰的な解法を考えます。与えられた数列の最初の分割位置について場合分けをします。たとえば、最初の区間として可能なものが次の 3 つだとします。・ ・ ・それぞれの場合について、・ の場合： に対する解 dp[2] ・ の場合： に対する解 dp[3] ・ の場合： に対する解 dp[4]があらかじめ求められているとすれば、・dp[1] = dp[2] + dp[3] + d… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fenakai00.hatenablog.com%2Fentry%2F2021%2F09%2F26%2F184634" title="089 - Partitions and Inversions（★7）の解説 - めもめも" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-09-26 18:46:34 rich https://enakai00.hatenablog.com/entry/2021/09/26/184634 1.0 100%