[ARC126D] Pure Straight 题解

题意

给定一个有 \(N\) 个正整数的序列 \(A=(A_1,A_2,\cdots,A_N)\)，且 \(A_i \in \left[1,K\right]\)。

你可以对这个序列做如下操作若干次。

交换两个相邻的元素，也就是选出 \(i\) 和 \(j\) 满足 \(\lvert i - j\rvert = 1\) 并交换 \(A_i\) 和 \(A_j\)。

找到最小的操作数使 \(A\) 满足如下条件。

\(A\) 包含 \((1,2,\cdots,K)\) 作为一个相接的子序列，也就是对于任意正整数 \(n \le N−K+1\) 满足 \(A_n=1,A_{n+1}=2,\cdots,A_{N−K+1}=K\)。

\(2 \le K \le 16, K \le N \le 200\)。

题解

设 \(f_{i,S}\) 表示在前 \(i\) 个元素中选取的数字构成集合 \(S\) 并将其按序排列并将其末尾元素移动到 \(i\) 的最小操作次数。

转移的话考虑两种情况：

• 将数 \(A_i\) 加入集合 \(S\)，那么贡献为当前集合中比 \(A_i\) 大的数的个数，即逆序对个数；
• 不将数 \(A_i\) 加入集合 \(S\)，那么贡献可以考虑将在 \(S\) 中的数全部右移或将未在 \(S\) 中的数全部左移，两种操作方案取 \(\min\) 即可。

复杂度为 \(\mathcal{O}(n2^k)\)，可以通过本题。

Code

//D
#include <bits/stdc++.h>

typedef int bitType;
typedef int valueType;
typedef std::vector<valueType> ValueVector;

typedef std::function<valueType(bitType)> BitCountFunction;

constexpr valueType MAX = INT_MAX >> 1;

int main() {
    valueType N, K;

    std::cin >> N >> K;

    bitType const S = (1 << K) - 1;

    ValueVector source(N);

    for (auto &iter: source)
        std::cin >> iter;

    BitCountFunction count = [](bitType n) -> valueType {
        return __builtin_popcount(n);
    };

    ValueVector dp(S + 1, MAX);

    dp[0] = 0;

    for (valueType i = 0; i < N; ++i) {
        bitType const mask = (1 << (source[i] - 1)) - 1, bit = 1 << (source[i] - 1);

        for (bitType j = S; j >= 0; --j) {
            if ((j & bit) == 0)
                dp[j | bit] = std::min(dp[j | bit], dp[j] + count(j & (~mask)));

            dp[j] = dp[j] + std::min(count(j), K - count(j));
        }
    }

    std::cout << dp[S] << std::endl;

    return 0;
}