思路
首先如果直接算每一个段有三个决策
左/右 上/下 跨不跨过端点
这样的复杂度是((2^3)^{22})，显然是无法接受的
然后考虑怎么优化这个东西
首先左右这个决策是没有意义的
因为无论是左还是右，对答案的相对影响是不变的
其次考虑用a和b分别表示上下和跨不跨过端点的决策
然后退一下就可发现有很多种情况是可以归约的
大概成了这样
void dfs(int tmp, int res) {
if (res >= ans) return;
if (tmp > n) {
ans = res;
return;
}
if (cnt[t[tmp]] == 1 || pre[tmp]) {
dfs(tmp + 1, res);
return;
}
int now;
a[tmp] = 0;
b[tmp] = 0;
now = res;
fu(i, 1, tmp - 1)
if (!(a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;
dfs(tmp + 1, now);
a[tmp] = 0;
b[tmp] = 1;
now = res;
fu(i, 1, tmp - 1) {
if ((a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;
if (!(a[i] ^ b[i]) && nxt[i] > tmp) ++now;
}
dfs(tmp + 1, now);
a[tmp] = 1;
b[tmp] = 0;
now = res;
fu(i, 1, tmp - 1)
if ((a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;
dfs(tmp + 1, now);
a[tmp] = 1;
b[tmp] = 1;
now = res;
fu(i, 1, tmp - 1) {
if (!(a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;
if ((a[i] ^ b[i]) && nxt[i] > tmp) ++now;
}
dfs(tmp + 1, now);
}
这样是可以得到64分的高分的
但是并不够
继续考虑怎么压缩状态
发现前面的每个已经决策的区间对当前区间的影响只有a和b的异或和
所以每次只枚举a和b的异或和
但是a和b的异或和相等的情况有两种
但是这两种对后面决策的影响都是相同的
所以直接贪心取最小的就可以了
复杂度(n*2^{n/2})
AC代码
//Author: dream_maker
#include<bits/stdc++.h>
using namespace std;
//----------------------------------------------
//typename
typedef long long ll;
//convenient for
#define fu(a, b, c) for (int a = b; a <= c; ++a)
#define fd(a, b, c) for (int a = b; a >= c; --a)
#define fv(a, b) for (int a = 0; a < (signed)b.size(); ++a)
//inf of different typename
const int INF_of_int = 1e9;
const ll INF_of_ll = 1e18;
//fast read and write
template <typename T>
void Read(T &x) {
bool w = 1;x = 0;
char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') w = 0, c = getchar();
while (isdigit(c)) {
x = (x<<1) + (x<<3) + c -'0';
c = getchar();
}
if (!w) x = -x;
}
template <typename T>
void Write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9) Write(x / 10);
putchar(x % 10 + '0');
}
//----------------------------------------------
const int N = 50;
int t[N], n, ans;
int pre[N], nxt[N], last[N], cnt[N];
bool a[N], b[N], mark[N];
//a 走上面(0)还是下面(1)
//b 不跨过(0)还是跨过(1)
int T;
/*void dfs(int tmp, int res) {
if (res >= ans) return;
if (tmp > n) {
ans = res;
return;
}
if (cnt[t[tmp]] == 1 || pre[tmp]) {
dfs(tmp + 1, res);
return;
}
int now;
a[tmp] = 0;
b[tmp] = 0;
now = res;
fu(i, 1, tmp - 1)
if (!(a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;
dfs(tmp + 1, now);
a[tmp] = 0;
b[tmp] = 1;
now = res;
fu(i, 1, tmp - 1) {
if ((a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;
if (!(a[i] ^ b[i]) && nxt[i] > tmp) ++now;
}
dfs(tmp + 1, now);
a[tmp] = 1;
b[tmp] = 0;
now = res;
fu(i, 1, tmp - 1)
if ((a[i] ^ b[i]) && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now;
dfs(tmp + 1, now);
a[tmp] = 1;
b[tmp] = 1;
now = res;
fu(i, 1, tmp - 1) {
if (!(a[i] ^ b[i]) && nxt[i] > nxt[tmp]) ++now;
if ((a[i] ^ b[i]) && nxt[i] > tmp) ++now;
}
dfs(tmp + 1, now);
}*/
void dfs(int tmp, int res) {
if (res >= ans) return;
if (tmp > n) {
ans = res;
return;
}
if (cnt[t[tmp]] == 1 || pre[tmp]) {
dfs(tmp + 1, res);
return;
}
int now1, now2;
mark[tmp] = 0;
now1 = now2 = res;
fu(i, 1, tmp - 1) {
if (!mark[i] && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now1;
if (!mark[i] && nxt[i] > nxt[tmp]) ++now2;
if (mark[i] && nxt[i] > tmp) ++now2;
}
dfs(tmp + 1, min(now1, now2));
mark[tmp] = 1;
now1 = now2 = res;
fu(i, 1, tmp - 1) {
if (mark[i] && nxt[i] > tmp && nxt[i] < nxt[tmp]) ++now1;
if (mark[i] && nxt[i] > nxt[tmp]) ++now2;
if (!mark[i] && nxt[i] > tmp) ++now2;
}
dfs(tmp + 1, min(now1, now2));
}
void solve() {
Read(n);
fu(i, 1, n) pre[i] = nxt[i] = last[i] = cnt[i] = 0;
fu(i, 1, n) {
Read(t[i]);
++cnt[t[i]];
if (last[t[i]]) {
pre[i] = last[t[i]];
nxt[last[t[i]]] = i;
} else {
last[t[i]] = i;
}
}
ans = INF_of_int;
dfs(1, 0);
printf("%d
", ans);
}
int main() {
freopen("input.txt","r",stdin);
Read(T);
while (T--) solve();
return 0;
}