便宜上、\(P_0 \coloneqq (1, 2, \ldots, L)\) とおきます。 また、\(i\) 回目の操作後に \(A = P_i\) を満たして \(C_i\) 円を獲得することを、単に \(i\) を達成すると呼びます。

\((0, 1, 2, \ldots, N)\) の部分列 \((i_0 \coloneqq 0, i_1, i_2, \ldots, i_n)\) について、 \(i_1, i_2, \ldots, i_n\) のすべてを達成できるためには、

(\(\star\)) すべての \(j = 1, 2, \ldots, n\) で \(\mathrm{inv}(P_{i_{j-1}}, P_{i_j}) \leq i_j - i_{j-1}\) が成り立つ

ことが必要十分です。 ここで、\(\mathrm{inv}(P, P')\) は、\(P\) を隣接 \(2\) 項の swap によって \(P'\) に変形するために必要な swap 回数の最小値を表し、\(P^{-1}P'\) の転倒数で与えられます。

本問題は、上の条件 (\(\star\)) を満たすように達成する数の列 \((i_0 = 0, i_1, i_2, \ldots, i_n)\) をえらんで、利得 \(C_{i_1} + C_{i_2} + \dots + C_{i_n}\) を最大化する問題です。 動的計画法でこの問題を解きます。\(i = 0, 1, \ldots, N\) について

\(\mathrm{dp}[i] = \)（最後に達成したのが \(i\) であるときのそれまでの利得としてありえる最大値）

とおくと、\(\mathrm{dp}[0] = 0\) および \(i = 1, 2, \ldots, N\) について

\[ \mathrm{dp}[i] = \max_{\substack{0 \leq j \lt i,\\ \mathrm{inv}(P_j, P_i) \leq i-j}} \mathrm{dp}[j] + C_i \tag{1} \]

という漸化式が成り立ち、本問題の答えは \(\max_{i = 0}^N \mathrm{dp}[i]\) で得られます。

ここで、\((1, 2, \ldots, L)\) の任意の順列 \(P\) から任意の順列 \(P'\) に隣接 \(2\) 項の swap を高々 \(D \coloneqq L(L-1)/2\) 回繰り返して変形できる、すなわち \(\mathrm{inv}(P, P') \leq D\) であることに注意すると、最適な達成列 \((i_0 \coloneqq 0, i_1, i_2, \ldots, i_n)\) においては、すべての \(j = 1, 2, \ldots, n\) で \(i_j - i_{j-1} \lt 2D\) が成り立つことがわかります（ もしそうでなければ、\(i_{j-1}\) と \(i_j\) の間に、\({i_{j-1} + D}\) も追加で達成することができるため最適性に反します）。

よって、\(\mathrm{dp}[i]\) を求める際には \(\mathrm{dp}[i-2D+1], \ldots, \mathrm{dp}[i-1]\) の \(O(L^2)\) 個の要素だけを参照すればよく、上記の式 (1) は

\[ \mathrm{dp}[i] = \max_{\substack{\max\lbrace 0, i - 2D+1 \rbrace \lt j \lt i,\\ \mathrm{inv}(P_j, P_i) \leq i-j}} \mathrm{dp}[j] + C_i \]

に置き換えられます。 この漸化式を用いれば、すべての \(i = 1, 2, \ldots, N\) に対する \(\mathrm{dp}[i]\) を計算することが、\(O(NL^2)\) 本ある遷移それぞれについて転倒数を \(O(L^2)\) 時間で計算して、全体で \(O(NL^4)\) 時間で可能です。