Preface
一定要剪枝：如果搜到的答案 \(\geq\) 当前的最优答案就不要继续搜了！！！不剪枝跑 \(T = 100\) 只能沦为暴力同分！！！
Solution
- 首先对于每组地铁站，有 \(8\) 种换乘情况。标注一遍：
- 直接爆搜（\(\mathcal O(n8^{\frac{n}{2}})\)）在 \(n \leq 44\) 的情况下不现实。考虑优化状态，具体地，我们可以先把 ①② 两个连线方式合并起来看（右下角截进了搜狗输入法的河童皮肤，无伤大雅）：
- 同理可以发现 ③④、⑦⑧ 产生的贡献在无论何时都是一样的，那么我们不妨丢掉 ④⑦ 考虑。现在状态数变成了 \(4\) 个，爆搜已经可以获得比较可观的分数了（\(\mathcal O(n4^{\frac{n}{2}})\)）。考虑继续优化，但是我们已经无法再合并状态了。
- 我们在搜索的时候将所有换乘站连线按照 \(L\) 排序，那么你会发现搜到一对站点时，对它产生交点贡献的只会和前面的换乘站的 \(R\) 有关系（这同样是因为我们在先前丢掉了 ④⑦ 而非 ③⑧）。
- 更具体地，根据在 \(0\) 号线的「上方」的 \(R\) 和「下方」的 \(R\)，我们可以把贡献分为两个部分。容易发现在剩下来的四种状态中，①⑧ 的贡献都是「上方」的 \(R\) 增加 \(1\)，而 ③⑥ 反之。
- 所以这样我们就把每次的抉择变成了两个：对「上方」的 \(R\) 贡献还是「下方」的 \(R\) 贡献。而对上方贡献时，新增的交点个数可以贪心地选择 ①⑧ 中较小的一个；下方同理。目前时间复杂度 \(\mathcal O(n2^{\frac{n}{2}})\)。
- 考虑如何优化贡献的计算：不难发现计算时产生交点的 \(R\) 是一段连续的区间，具体地：
- 选择 ① 时，一个 \(R\) 贡献当且仅当：它在「上方」，它的 \(R\) 在当前区间 \([l, r]\) 内（开区间、闭区间可以灵活抉择，毕竟每个位置上只会有一个换乘站）。
- 选择 ⑧ 时，一个 \(R\) 贡献当且仅当：它在「上方」，它的 \(R\) 在当前区间 \([r, \inf)\) 内，或它在「下方」，它的 \(R\) 在当前区间 \([l, \inf)\) 内。
- 选择 ③ 时，一个 \(R\) 贡献当且仅当：它在「下方」，它的 \(R\) 在当前区间 \([l, r]\) 内。
- 选择 ⑥ 时，一个 \(R\) 贡献当且仅当：它在「上方」，它的 \(R\) 在当前区间 \([l, \inf)\) 内，或它在「下方」，它的 \(R\) 在当前区间 \([r, \inf)\) 内。
- 找每种贡献明显可以使用树状数组优化。时间复杂度 \(\mathcal O(2^{\frac{n}{2}}\log n)\)（但是一定要加上开头所述的优化！！！1）。
Code
- \(8\) 个状态爆搜：没有写过。
- \(4\) 个状态爆搜（交上去不是 TLE 而是 WA 36 pts，贡献可能算错了吧 /ll 我大为震撼）：
#define MAXN 45
int lst[MAXN], status[MAXN];
struct Metro {
int l, r;
Metro () {}
Metro (int L, int R) : l(L), r(R) {}
const bool operator < (const Metro& k) const {
return l < k.l;
}
};
std::vector<Metro> lines;
// status = 0
// -----------
// | |
// =====*=========*=====
//
//
// status = 1
// -------------------
// | |
// =====*=========*===== |
// | |
// ---------
// status = 2
//
//
// =====*=========*=====
// | |
// -----------
// status = 3
// ---------
// | |
// =====*=========*===== |
// | |
// -------------------
int ans = 0x3f3f3f3f;
void dfs(int u = 0, int sum = 0) {
if (sum >= ans) return;
if (u == lines.size()) { ans = sum; return; }
int up0 = 0, down1 = 0, down2 = 0, up3 = 0;
for (int i = 0; i < u; ++i) {
if (status[i] == 0) {
up0 += lines[i].r < lines[u].r && lines[i].r > lines[u].l;
down1 += lines[i].r > lines[u].l;
up3 += lines[i].r > lines[u].r;
} else if (status[i] == 1) {
down1 += lines[i].r > lines[u].r;
down2 += lines[i].r < lines[u].r && lines[i].r > lines[u].l;
up3 += 1;
} else if (status[i] == 2) {
down1 += lines[i].r > lines[u].r;
down2 += lines[i].r < lines[u].r && lines[i].r > lines[u].l;
up3 += lines[i].r > lines[u].l;
} else /*status[i] == 3*/ {
up0 += lines[i].r < lines[u].r && lines[i].r > lines[u].l;
down1 += 1;
up3 += lines[i].r > lines[u].r;
}
}
if (up0 < up3)
status[u] = 0, dfs(u + 1, sum + up0);
else status[u] = 3, dfs(u + 1, sum + up3);
if (down1 < down2)
status[u] = 1, dfs(u + 1, sum + down1);
else status[u] = 2, dfs(u + 1, sum + down2);
}
int main() {
int T = read<int>();
while (T--) {
int N = read<int>();
for (int i = 1; i <= N; ++i) {
int a = read<int>();
if (lst[a]) lines.push_back(Metro(lst[a], i));
lst[a] = i;
}
std::sort(lines.begin(), lines.end());
dfs(0); print<int>(ans, '\n');
memset(lst, 0, sizeof(lst));
lines.clear(), ans = 0x3f3f3f3f;
}
return 0;
}
- 树状数组满分做法，随便卡了点常数，其他部分都一样就不放了：
int t0[MAXN], t1[MAXN], Z = 45, ans = 0x3f3f3f3f;
void add0(int x, int v) { while (x <= Z) t0[x] += v, x += x & (-x); }
void add1(int x, int v) { while (x <= Z) t1[x] += v, x += x & (-x); }
int query0(int x) { int ans = 0; while (x) ans += t0[x], x -= x & (-x); return ans; }
int query1(int x) { int ans = 0; while (x) ans += t1[x], x -= x & (-x); return ans; }
void dfs(int u = 0, int sum = 0) {
if (sum >= ans) return;
if (u == lines.size()) { ans = std::min(ans, sum); return; }
int l = lines[u].l, r = lines[u].r, pr0 = query0(r), pr1 = query1(r), pr2 = u - pr0 - pr1;
pr0 -= query0(l), pr1 -= query1(l);
// choose :
// 0 -> pr0
// 1 -> pr0 + pr2
// 2 -> pr1
// 3 -> pr1 + pr2
// printf("%s%d %d %d %d %d\n", std::string(u * 4, ' ').c_str(), u, pr0, pr1, pr2, pr3);
// printf("%s%d %d\n", std::string(u * 4, ' ').c_str(), std::min(pr0, pr1 + pr2), std::min(pr1, pr0 + pr3));
add0(r, 1);
dfs(u + 1, sum + std::min(pr0, pr1 + pr2));
add0(r, -1), add1(r, 1);
dfs(u + 1, sum + std::min(pr1, pr0 + pr2));
add1(r, -1);
// printf("%s%d\n", std::string(u * 4, ' ').c_str(), ans);
}