又来给 do_while_true 大佬交作业了，所以本篇题解仅仅是对 该篇题解 进行补充说明的。
本篇题解适用于像我这样的小萌新，那篇题解适合大佬食用。
Part 1：
为什么我们要用状压dp？
因为题解里面写了要用。
因为我们要进行对答案集合内的情况取最小值的操作，可以使用dp。并且 \(K \le 16\) 但 \(N \le 200\)。所以肯定是使用状压dp或者倍增优化dp。又发现是对一个集合里面的数进行的操作，且 \(2^K\) 的数组能开下，所以应该是状压dp。
Part 2：
状态的设计和转移。
跟着题解设计就行。
我们设 \(f_S\) 表示已经将 \(S\) 这个集合里的数字将题目要求的顺序排好的代价。我们插入一个新的数，她既可能去前面作为前面的排列中的一个数，也有可能去后面作为后面的排列中的这个数。对于集合整体，既可以将在这个集合里的数汇总起来，也可以将不在这个集合的数交换出去。
综上所述，我们可以得到这样的式子：
\(\forall x \notin S,f(S | (1 << x) = min\{f(S | (1 << x)),f(S) + popcount(s \& (~((1 << x) - 1)))\}\)
\(f(S) = min\{popcount(S),k - popcount(S)\}\)
Part 3：
上代码！！！！
点击查看代码
#include <bits/stdc++.h>
namespace hello_world_djh {
template <typename T>
T read() {
T x = 0, f = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-')
f = ~f + 1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ '0');
return x * f;
}
const int N = 210, K = 16, INF = 0x3f3f3f3f;
int n = read<int>(), k = read<int>();
int f[(1 << K) + 10];
#define sum __builtin_popcount
int main() {
for (int i = 1; i <= (1 << k) - 1; i++)
f[i] = INF;
for (int i = 1; i <= n; i++) {
int x = read<int>() - 1;
for (int j = (1 << k) - 1; ~j; j--)
if (f[j] != INF) {
if (!(j & (1 << x)))
f[j | (1 << x)] = std::min(f[j | (1 << x)], f[j] + sum(j & (~((1 << x) - 1))));
f[j] += std::min(sum(j), k - sum(j));
}
}
printf("%d\n", f[(1 << k) - 1]);
return 0;
}
};
int main() {
hello_world_djh::main();
return 0;
}