http://acm.hdu.edu.cn/showproblem.php?pid=4385
状态压缩需要好好理解啊；
又是一道 状态压缩的题 ，一开始觉的和 poj 的一道题有点像 ，特地先做了一下那个题 再回来做的这道题，结果还是没做出来 这到，最后看了 解题报告：
题意:
一个人在搬砖，初始位置在(x0,y0)，目的地也是(x0,y0)，给你n（n<=20）块砖的位置(xi,yi)，规定两点之间时间耗费为欧几里德距离的平方，此人一次可以搬不超过两块砖，
问你最少的时间花费并给出方案.
官方题解：
简单状态DP.
需要注意的是,由于耗费的时间是路长的平方,所以一次性取两点的代价并不一定比分两次取小.
每次从building出发
对于当前状态i和当前未纳入状态的点j
t = i | (1<<j);
dp[t] = dp[i] + dist[n][j] + dist[j][n];
对于未纳入状态t的点k
p = t | (1<<k);
dp[k] = dp[i] + dist[n][j] + dist[j][k] + dist[k][n];
关于取点的输出,可以记录当前状态i的前一状态pre[i],两状态取异或即可.每次出发后会取回1~2点 即(Ai1,Ai2)或Ai1
由于各点的序号是不相同的,只需要比较每次出发取到的较小的序号.
将这些点或点对取其中序号较小的作为关键字按升序排序输出即可.
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 30
15 #define eps 1e-8
16 #define inf 100000000
17 #define N 4000000
18 #define ll __int64
19 using namespace std;
20 struct node
21 {
22 int x;
23 int y;
24 }a[maxn] ,ans[maxn];
25 int cmp(node a,node b)
26 {
27 return a.x < b.x;
28 }
29 int dp[N] ,dis[maxn][maxn],pre[N];
30 int main()
31 {
32 int i,j,n,t,tmp,p,tp,k,x,y;
33 int cas = 0 ;
34 //freopen("data.txt","r",stdin);
35 scanf("%d",&t);
36 while(t--)
37 {
38 scanf("%d%d",&x,&y);
39 scanf("%d",&n);
40 a[n].x = x;
41 a[n].y = y;
42 for(i = 0;i< n;i++)
43 {
44 scanf("%d%d",&a[i].x,&a[i].y);
45 }
46 for(i = 0; i <=n;i++)
47 {
48 for(j = i+1;j<=n;j++)
49 {
50 dis[i][j] = dis[j][i] = (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)* (a[i].y - a[j].y);
51 }
52 }
53 memset(dp,0x3f,sizeof(dp));
54 dp[0] = 0 ;
55 int stat = (1<<n) - 1;
56 for(i = 0 ; i <= stat ;i++)
57 {
58 for(j = 0 ; j<n;j++)
59 {
60 if(!(i&(1<<j)))
61 {
62 tp = i|1<< j;
63 tmp = dp[i] + 2*dis[j][n];
64 if(dp[tp] > tmp)
65 {
66 dp[tp] = tmp;
67 pre[tp] = i;
68 }
69
70 for(k = 0 ; k< n;k++)//如果 一次 去两块
71 {
72 if(!(tp&(1<<k)))
73 {
74 p = tp|1<<k;
75 tmp = dp[i] + dis[j][n] + dis[j][k] + dis[k][n] ;
76 if(dp[p] > tmp)
77 {
78 dp[p] = tmp;
79 pre[p] = i;// 注意 这里的状态 是记录 去两块 之前的 i
80 }
81 }
82 }
83 }
84 }
85
86 }
87 printf("Case %d:\n",++cas);
88 printf("%d\n",dp[stat]);
89 int t = stat;
90 int num = 0;
91
92 while(t)
93 {
94 bool flag = false ;
95 int tmp = t^pre[t];
96 ans[num].y = 25 ;//用来记录一次 取两个 个的第二个元素 （25 表示初始化 没有）
97 for(i = 0 ; i < n;i++)
98 {
99 if((tmp>>i)&1)
100 {
101 if(!flag)
102 {
103 ans[num].x = i;
104 flag = true ;
105 }
106 else ans[num].y = i;
107 }
108 }
109
110 t = pre[t];
111 num ++;
112 }
113
114 sort(ans,ans+num,cmp);
115
116
117 for(i = 0 ; i< num;i++)
118 {
119 if(i == 0)printf("%d",ans[i].x + 1);
120 else printf(" %d",ans[i].x + 1);
121
122 if(ans[i].y < 25) printf(" %d",ans[i].y + 1) ;
123 }
124 puts("");
125
126
127
128
129 }
130 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 30
15 #define eps 1e-8
16 #define inf 100000000
17 #define N 4000000
18 #define ll __int64
19 using namespace std;
20 struct node
21 {
22 int x;
23 int y;
24 }a[maxn] ,ans[maxn];
25 int cmp(node a,node b)
26 {
27 return a.x < b.x;
28 }
29 int dp[N] ,dis[maxn][maxn],pre[N];
30 int main()
31 {
32 int i,j,n,t,tmp,p,tp,k,x,y;
33 int cas = 0 ;
34 //freopen("data.txt","r",stdin);
35 scanf("%d",&t);
36 while(t--)
37 {
38 scanf("%d%d",&x,&y);
39 scanf("%d",&n);
40 a[n].x = x;
41 a[n].y = y;
42 for(i = 0;i< n;i++)
43 {
44 scanf("%d%d",&a[i].x,&a[i].y);
45 }
46 for(i = 0; i <=n;i++)
47 {
48 for(j = i+1;j<=n;j++)
49 {
50 dis[i][j] = dis[j][i] = (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)* (a[i].y - a[j].y);
51 }
52 }
53 memset(dp,0x3f,sizeof(dp));
54 dp[0] = 0 ;
55 int stat = (1<<n) - 1;
56 for(i = 0 ; i <= stat ;i++)
57 {
58 for(j = 0 ; j<n;j++)
59 {
60 if(!(i&(1<<j)))
61 {
62 tp = i|1<< j;
63 tmp = dp[i] + 2*dis[j][n];
64 if(dp[tp] > tmp)
65 {
66 dp[tp] = tmp;
67 pre[tp] = i;
68 }
69
70 for(k = 0 ; k< n;k++)//如果 一次 去两块
71 {
72 if(!(tp&(1<<k)))
73 {
74 p = tp|1<<k;
75 tmp = dp[i] + dis[j][n] + dis[j][k] + dis[k][n] ;
76 if(dp[p] > tmp)
77 {
78 dp[p] = tmp;
79 pre[p] = i;// 注意 这里的状态 是记录 去两块 之前的 i
80 }
81 }
82 }
83 }
84 }
85
86 }
87 printf("Case %d:\n",++cas);
88 printf("%d\n",dp[stat]);
89 int t = stat;
90 int num = 0;
91
92 while(t)
93 {
94 bool flag = false ;
95 int tmp = t^pre[t];
96 ans[num].y = 25 ;//用来记录一次 取两个 个的第二个元素 （25 表示初始化 没有）
97 for(i = 0 ; i < n;i++)
98 {
99 if((tmp>>i)&1)
100 {
101 if(!flag)
102 {
103 ans[num].x = i;
104 flag = true ;
105 }
106 else ans[num].y = i;
107 }
108 }
109
110 t = pre[t];
111 num ++;
112 }
113
114 sort(ans,ans+num,cmp);
115
116
117 for(i = 0 ; i< num;i++)
118 {
119 if(i == 0)printf("%d",ans[i].x + 1);
120 else printf(" %d",ans[i].x + 1);
121
122 if(ans[i].y < 25) printf(" %d",ans[i].y + 1) ;
123 }
124 puts("");
125
126
127
128
129 }
130 }