UVA10911 Forming Quiz Teams 复杂状态的DP （状压dp）

Bertha 。 2021-12-17 13:51 204阅读 0赞

## 题意：最优配对问题。空间里有n个点P 0 ,  P 1 , … , P n-1 ，你的任务是把它们配成n/2对（n是偶数），使得每个点恰好在一个点对中。所有点对中两点的距离之和应尽量小。n≤20, |x i |,|y i |,|z i |≤10000。 ##

## 分析：紫书P284-285，既然每个点都要配对，很容易把问题看成如下的多阶段决策过程：先确定P 0 和谁配对，然后是P 1 ，接下来是P 2 ，……，最后是P n-1 。按照前面的思路，设d(i)表示把前i个点两两配对的最小距离和，然后考虑第i个点的决策——它和谁配对呢？假设它和点j配对（j<i），那么接下来的问题应是“把前i-1个点中除了j之外的其他点两两配对”，它显然无法用任何一个d值来刻画——此处的状态定义无法体现出“除了一些点之外”这样的限制。当发现状态无法转移后，常见的方法是增加维度，即增加新的因素，更细致地描述状态。既然刚才提到了“除了某些元素之外”，不妨把它作为状态的一部分，设d(i,S)表示把前i个点中，位于集合S中的元素两两配对的最小距离和，则状态转移方程为：其中，|P i P j |表示点P i 和P j 之间的距离。方程看上去很不错，但实现起来有问题：如何表示集合S呢？由于它要作为数组d中的第二维下标，所以需要用整数来表示集合，确切地说，是\{0, 1, 2,…,n-1\}的任意子集（subset）。 ##

for(int i = 0; i < n; i++)
        for(int S = 0; S < (1<<n); S++) {
            d[i][S] = INF;
            for(int j = 0; j < i; j++) if(S & (1<<j))
            d[i][S] = min(d[i][S], dist(i, j) + d[i-1][S^(1<<i)^(1<<j)]);
        }

## 上面的方程可以进一步简化。事实上，阶段i根本不用保存，它已经隐含在S中了——S中的最大元素就是i。这样，可直接用d(S)表示“把S中的元素两两配对的最小距离和”，   则状态转移方程为： ##

d(S)=min{|PiPj |+d(S-{i}-{j})|j∈S, i=max{S}}

## 状态有![2^\{n\}][2_n] 个，每个状态有O(n)种转移方式，总时间复杂度为O(![n2^\{n\}][n2_n] )。      值得一提的是，不少用户一直在用这样的状态转移方程： ##

d(S)=min{|PiPj |+d(S-{i}-{j})|i, j∈S, }

## 它和刚才的方程很类似，唯一的不同是：i和j都是需要枚举的。这样做虽然也没错，但每个状态的转移次数高达O(n 2 )，总时间复杂度为O( )，比刚才的方法慢。这个例子再次说明：即使用相同的状态描述，减少决策也是很重要的。 ##

## 接下来出现了一个新问题：如何求出S中的最大元素呢？用一个循环判断即可。当S取遍\{0, 1, 2,…, n-1\}的所有子集时，平均判断次数仅为2。 ##

for(int S = 0; S < (1<<n); S++) {
        int i, j;
        d[S] = INF;
        for(i = 0; i < n; i++)
            if(S & (1<<i)) break;
        for(j = i+1; j < n; j++)
            if(S & (1<<j)) d[S] = min(d[S], dist(i, j) + d[S^(1>>i)^(1>>j)]);
    }

## 注意，在上述的程序中求出的i是S中的最小元素，而不是最大元素，但这并不影响答案。另外，j的枚举只需从i+1开始——既然i是S中的最小元素，则说明其他元素自然均比i大。最后需要说明的是S的枚举顺序。不难发现：如果S'是S的真子集，则一定有S'<S，因此若以S递增的顺序计算，需要用到某个d值时，它一定已经计算出来了。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int INF = 0x3f3f3f3f;
    const int maxn = 1010;
    int x[maxn], y[maxn];
    double d[1<<16];
    double dis(int a,int b){
        return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
    }
    int n, kase;
    int main(){
    	while(scanf("%d", &n) == 1 && n){
    		char s[maxn];
    		n <<= 1;
    		for(int i = 0; i < n; ++i){scanf("%s%d%d", s, &x[i], &y[i]);}
    		d[0] = 0;
    		for(int S = 1; S < (1 << n); ++S){
    			d[S] = INF;
    			int i, j;
    			for(i = 0; i < n; ++i) if(S & (1 << i)) break;
    			for(j = i + 1; j < n; ++j) if(S & (1 << j)) d[S] = min(d[S], dis(i, j) + d[S ^ (1 << i) ^ (1 << j)]);
    		}
    		printf("Case %d: %.2lf\n", ++kase, d[(1 << n) - 1]);
    	}
    	return 0;
    }

[2_n]: https://private.codecogs.com/gif.latex?2%5E%7Bn%7D
[n2_n]: https://private.codecogs.com/gif.latex?n2%5E%7Bn%7D