条件を満たす列

\(N\) が小さい範囲で実験してみます。

\(N = 5\) のときは条件を満たす並びは下記のようになります。

• 1 2 3 4 5
• 1 2 3 5 4
• 1 2 4 3 5
• 1 2 5 4 3
• 1 3 2 4 5
• 1 3 2 5 4
• 1 4 3 2 5
• 1 5 4 3 2
• 2 1 3 4 5
• 2 1 3 5 4
• 2 1 4 3 5
• 2 1 5 4 3
• 3 2 1 4 5
• 3 2 1 5 4
• 4 3 2 1 5
• 5 4 3 2 1

「昇順に並び替えた数列をいくつかの区間に分割し区間内で降順に並び替えた数列」が条件を満たす数列となりそうです。

たとえば、2 1 3 5 4 は 1 2, 3, 4 5 と分割してそれぞれ降順にしたものです。

並び替えのDP

\[ \begin{aligned} dp1[i][j]=左から i-1 個は条件を満たすよう並んでいる状態から、i 以上 j 以下までを昇順に並べるのに必要な回数 \\ dp2[i][j]=左から i-1 個は条件を満たすよう並んでいる状態から、i 以上 j 以下までを降順に並べるのに必要な回数 \end{aligned} \]

というDPを考えます。

また、

\[ sums[i][k] = H についてインデックス i未満の範囲にk 未満の数値はいくつあるか \]

を累積和を用いて、前準備 \(O(N^2)\), クエリ \(O(1)\) で取得できるようにします。

これで、\(dp1, dp2\) の値を \(O(N^2)\) で求められます。

// hrev[i]: H[i] が現れるインデックス
for (int i = 0; i < N; i++)
{
    var hi = hrev[i];
    dp1[i][i] = dp2[i][i] =sums[hi][i..];
    for (int j = i + 1; j < N; j++)
    {
        var hj = hrev[j];
        dp1[i][j] = dp1[i][j - 1] + sums[hj][j..];
        dp2[i][j] = dp2[i][j - 1] + sums[hj][i..] - ((j - i) - sums[hj][i..j]);
    }
}

\(dp1, dp2\) を元に下記のDPを考えます。

\[ dp[i] = i 以下の数値が条件を満たす状態になるために必要な操作回数 \]

\(dp1, dp2\) を用いて、下記のように記述できます。

\[ dp[j+1] =\min_{i \leq j} (dp[i] +\min(dp1[i][j], dp2[i][j]) ) \]

\(dp[N]\) が答えとなり、全体で \(O(N^2)\) となりました。