很不错的状压。
考虑先把最后作为答案的数聚到一起,再算它们的逆序对个数。
设 \(f_S\) 为当前选的数集合为 \(S\) 的答案。有转移:
- 选 \(a_i\),答案加上之前选的比它大的数;
- 不选 \(a_i\),此时需要把左边的数或者右边的数往中间挪一个,答案加上左右两端的最小值。
这样算贡献感觉挺巧妙的。
code
// Problem: D - Pure Straight
// Contest: AtCoder - AtCoder Regular Contest 126
// URL: https://atcoder.jp/contests/arc126/tasks/arc126_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define ppc(x) __builtin_popcount(x)
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 210;
const int maxm = (1 << 16) + 50;
int n, m, f[maxm];
void solve() {
mems(f, 0x3f);
f[0] = 0;
scanf("%d%d", &n, &m);
for (int i = 0, x; i < n; ++i) {
scanf("%d", &x);
--x;
for (int S = (1 << m) - 1; ~S; --S) {
if ((~S) & (1 << x)) {
f[S | (1 << x)] = min(f[S | (1 << x)], f[S] + ppc(S & (~((1 << x) - 1))));
}
f[S] += min(ppc(S), m - ppc(S));
}
}
printf("%d\n", f[(1 << m) - 1]);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Straight AtCoder Regular Contest Purestraight atcoder regular contest atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 167 atcoder regular contest 164 atcoder regular contest 166 atcoder regular contest degree atcoder regular contest sliding atcoder regular contest builder atcoder regular contest 163