#8 C. Looking for Order （状压dp + 路径记忆）

柔情只为你懂 2022-06-17 08:29 178阅读 0赞

题目链接：[点击打开链接][Link 1]

# http://codeforces.com/contest/8/problem/C #

题意：

給定原点 ( sx, sy )，以及 N 個坐标 X, Y。每次至多选两个坐标，依序拜访完后，回到原点。问你最好的路径，使得总路径最小。兩個坐标的路径长为欧几里得距离的平方。

题解:

看N(N<=24)这么小,肯定可以状压dp。2^24。  
状压dp。

dp\[ i \] : 已完成 i 的拜访，此时的最小总花费。

如果用枚举的方法来更新DP，肯定会超时的。

关键在于：拜访是没有顺序的。然后在每一次拿东西的时候，都需要更新出两个状态，一种是只拿一个，另一种是拿两个。

由于与拜访的顺序无关，每个点又必须被使用，所以每次转移的時候，第一個选取的坐标就固定为还沒有拜访的座标里下标最小的。这么一來转移就只需要 O( N )。

dp时要记录一下路径就可以了。

复杂度：O（n\*2^n）。

AC代码：

//#pragma comment(linker, "/STACK:102400000,102400000")
    //#include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <set>
    #include <bitset>
    #include <iomanip>
    #include <list>
    #include <stack>
    #include <utility> 
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    const double eps = 1e-8;  
    const int INF = 1e9+7; 
    const ll inf =(1LL<<62) ;
    const int MOD = 1e9 + 7;  
    const ll mod = (1LL<<32);
    const int N =1e6+6; 
    const int M=100010;
    const int maxn=1001;
    #define mst(a) memset(a, 0, sizeof(a))
    #define M_P(x,y) make_pair(x,y)
    #define pi acos(-1.0)
    #define in freopen("in.txt","r",stdin) 
    #define rep(i,j,k) for (int i = j; i <= k; i++)  
    #define per(i,j,k) for (int i = j; i >= k; i--)  
    #define lson x << 1, l, mid  
    #define rson x << 1 | 1, mid + 1, r  
    const int lowbit(int x) { return x&-x; }
    int read(){ int v = 0, f = 1;char c =getchar();
    while( c < 48 || 57 < c ){if(c=='-') f = -1;c = getchar();}
    while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
    return v*f;}
    int dp[1<<24];
    int pre[1<<24];
    int dis[30][30],x[30],y[30];
    int n;
    int dfs1(int cur)//n*2^n 
    {
    	if(dp[cur]!=-1)return dp[cur];
    	dp[cur]=1e9;
    	for(int i=0;i<n;i++)
    	{
    		if(cur&(1<<i))
    		{
    		//	cout<<"i="<<(cur^(1<<i))<<endl;
    			int nxt = dfs1 (cur^(1<<i));
    			if(dp[cur] > nxt + dis[n][i] + dis[i][n] )
    			{
    				dp[cur] = nxt + dis[n][i] + dis[i][n];
    				//printf("dp[%d]=%d\n",cur,dp[cur]);
    				pre[cur] = cur^(1<<i);
    			}
    			for(int j=i+1;j<n;j++)
    			{
    				if(cur&(1<<j))
    				{			
    						//cout<<"j="<<(cur^(1<<j))<<endl;
    					//	cout<<"ij="<<(cur^(1<<i)^(1<<j))<<endl;
    						nxt = dfs1(cur^(1<<i)^(1<<j));
    						if(dp[cur] > nxt + dis[n][i] + dis[i][j] + dis[j][n])
    						{
    							dp[cur] = nxt + dis[n][i] + dis[i][j] + dis[j][n];
    						//	printf("dp[%d]=%d\n",cur,dp[cur]);
    							pre[cur] = cur^(1<<i)^(1<<j);
     						}
    				}
    
    			}
    			break;// 剪枝，不剪会TLE
    		}
    	}
    	return dp[cur];
    }
    int dfs2(int cur)
    {
    	if(cur)
    	{
    		for(int i=0;i<n;i++)
    		{
    			//if((cur^cur^(1<<i))||cur^cur^(1<<i)&&(1<<i))
    			if((cur^pre[cur])&(1<<i))	
    			{
    				cout<<i+1<<" ";
    			}
    		}
    		cout<<"0 ";//回到原点 
    		dfs2(pre[cur]);
    	}
    }
    int main()
    {
    	cin>>x[0]>>y[0];
    	cin>>n;
    	x[n]=x[0];y[n]=y[0];
    	for(int i=0;i<n;i++)
    	{
    		cin>>x[i]>>y[i];
    	}
    	for(int i=0;i<=n;i++)
    	{
    		for(int j=0;j<=n;j++)
    		{
    			dis[i][j]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
    		}
    	}
    	memset(dp,-1,sizeof(dp));
    	dp[0]=0;
    	cout<<dfs1((1<<n)-1)<<endl;
    //	cout<<dp[(1<<n)-1]<<endl; //一样的 
    	cout<<"0 ";
    	dfs2((1<<n)-1);
    	cout<<endl;
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/8/problem/C