题解 P4005 【小 Y 和地铁（metro）】

· · 题解

我的博客：http://www.cnblogs.com/david--lj/p/8535949.html 题意：一条线段，给定n个点(n<=44)其中每个点可能对应另外一个点。如果一个点有对应点，那么就要用曲线连接这两个点。这些曲线会有许多交点（不存在3线共点）求交点最少个数。

对于数据范围，我们可以发现是二进制暴搜，但是，为了剪枝，还是写dfs

我们发现，对于两个点，有6中连线方式:

复杂度：O(6^(n/2)) 咕咕咕

我们发现，如果把2，3画在一起，他们一定是一个圆环，且包住了整条线段，假如有一条新的线段，我们发现，那条线段要么和2，3都没交点，要么都有交点。也就是说对于两个点，用2还是用3对答案的贡献都是一样的。同理4，5也一样.

这样只用考虑4中情况了：复杂度：O(4^(n/2))还是咕咕咕

然后怎么优化？有的大佬用模拟退火（%%%%%%%%%%%）但我并不会模拟退火。

我们试着将1和2画在一起，我们发现，又是一个环，但这个环有点特殊，对在这两个点左边的点右侧的线段影响相同（在将所有线段排序后进行dfs）但左侧的点对于1或2的答案贡献是不同的。

thus，我们只需在dfs时，计算1，2的产生的答案贡献哪个更少，就用那个4，6同理。 代码中用树状数组优化 复杂度：O(2^(n/2))正常

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 50
int lowbit(int x){return x&-x;} 
struct treearr{
    int c[maxn],siz;
    void init(int p){int i;for(i=1;i<=p;++i)c[i]=0;siz=p;}
    void add(int x,int d){while(x<=siz){c[x]+=d;x+=lowbit(x);}}
    int sum(int x){int res=0;while(x){res+=c[x];x-=lowbit(x);}return res;}
    int query(int l,int r){return sum(r)-sum(l-1);}
};
treearr up,down;
int n,a[maxn],pos,l[maxn],r[maxn],ans;
void dfs(int st,int sum){
    if(st>pos){
        ans=min(ans,sum);return;
    }
    if(sum>ans)return;
    int i;
    int a1=min(up.query(l[st],r[st]),down.query(l[st],n)+up.query(r[st],n));
    up.add(r[st],1);dfs(st+1,sum+a1);up.add(r[st],-1);
    int a2=min(down.query(l[st],r[st]),up.query(l[st],n)+down.query(r[st],n));
    down.add(r[st],1);dfs(st+1,sum+a2);down.add(r[st],-1);
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int i,j;scanf("%d",&n);ans=1<<30;
        for(i=1;i<=n;++i)scanf("%d",&a[i]);
        pos=0;
        for(i=1;i<=n;++i)
            for(j=i+2;j<=n;++j)if(a[i]==a[j])
            {
                l[++pos]=i,r[pos]=j;break;
            }
        up.init(n);down.init(n);
        dfs(1,0);
        printf("%d\n",ans);
    }
}