P4005题解

闲来无事写篇题解

题面传送门

简要题意

一条线段上有 \(n\) 个点成对连接，求所连的线最小交点数。

思路

看到题目中 \(n \le 44\) 自然想到最终复杂度大约在 \(O (2 ^ \frac{n}{2})\) 左右。
经过思考不难发现不论如何两地铁站之间有且只有以下八种方式进行连接：

显然可以暴搜解决，搜索复杂度为 \(O(8 ^ \frac{n}{2})\)，每次搜索结束还需要 \(O(n)\) 统计答案，还有一个复杂度为 \(O(n ^ 2)\) 的预处理，不足以通过此题。

考虑优化，由下图可知左侧与右侧方案拼在一起便是绕线段一圈，与其他方案组合时是等效的，时间复杂度优化至 \(O(4 ^ \frac{n}{2})\)：

但是它仍无法通过本题，复杂度瓶颈依然在于搜索，思考统计答案的过程，是由左向右扫的，故如果此状态并不会对左侧产生影响，我们就可以将它们剪去：

在转移时只需要四选二即可，此时复杂度已经优化至 \(O(n \cdot 2 ^ \frac{n}{2})\) 经过计算可以发现极限数据依然会超时。

所以我们拿出树状数组来统计答案，即可通过本题。

code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 50;
int n, m = 0x7fffffff, a[N], state[N], l[N], r[N], tot;
struct BIT
{
	int tr[N], siz;
	inline void init(int s) {memset(tr, 0, sizeof(tr)); siz = s;}
	inline int lowbit(int x) {return x & -x;}
	inline void add(int x, int y) {while(x <= siz) tr[x] += y, x += lowbit(x);}
	inline int query(int x) {int ret = 0; while(x) ret += tr[x], x -= lowbit(x); return ret;}
	inline int query_(int x, int y) {return query(y) - query(x - 1);}
}u, d;
inline void dfs(int st, int sum = 0)
{
	if(sum > m) return;
	if(st > tot)
	{
		m = min(m, sum);
		return;
	}
	int a = min(u.query_(l[st], r[st]), d.query_(l[st], n) + u.query_(r[st], n));
	u.add(r[st], 1);
	dfs(st + 1, sum + a);
	u.add(r[st], -1);
	int b = min(d.query_(l[st], r[st]), u.query_(l[st], n) + d.query_(r[st], n));
	d.add(r[st], 1);
	dfs(st + 1, sum + b);
	d.add(r[st], -1);
}
inline void solve()
{
	cin >> n;
	tot = 0;
	for(int i = 1; i <= n; ++i)
		cin >> a[i], state[i] = 1;
	for(int i = 1; i <= n; ++i) for(int j = i + 1; j <= n; ++j) if(a[i] == a[j])
	{
		l[++tot] = i, r[tot] = j;
		break;
	}
	u.init(n);
	d.init(n);
	m = 0x7fffffff;
	dfs(1);
	cout << m << endl;
}
signed main ()
{
#ifndef ONLINE_JUDGE
    freopen ("test.in", "r", stdin);
    freopen ("test.out", "w", stdout);
#endif
	ios::sync_with_stdio (0);
	int T;
	cin >> T;
	while(T--)
		solve();
	return 0;
}