dp [ k ] 代表k状态拿了哪些物品...
如果直接枚举k..再枚举第一个物品.再枚举第二个物品..来更新dp...铁定超时...
注意的是..小女孩每次出去拿的顺序是可以任意换的.不影响最终结果..所以不妨给小女孩规定一个拿的大致顺序..每次冲着没拿的序号最小的去..然后看是否要顺便再拿另一个...
Program:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<algorithm>
#define ll long long
#define oo 1000000007
#define pi acos(-1.0)
#define MAXN 24
using namespace std;
int girl[2],objects[MAXN][2],dp[1<<MAXN],pre[1<<MAXN];
int arc[MAXN+1][MAXN+1];
int dis(int ax,int ay,int bx,int by)
{
int x=ax-bx,y=ay-by;
return x*x+y*y;
}
int main()
{
int n,i,x,t,p,goal;
int temp;
while (~scanf("%d%d",&girl[0],&girl[1]))
{
scanf("%d",&n);
for (i=0;i<n;i++) scanf("%d%d",&objects[i][0],&objects[i][1]);
for (i=1;i<=n;i++) arc[i][0]=arc[0][i]=dis(girl[0],girl[1],objects[i-1][0],objects[i-1][1]);
for (i=1;i<=n;i++)
for (x=i;x<=n;x++)
arc[i][x]=arc[x][i]=dis(objects[i-1][0],objects[i-1][1],objects[x-1][0],objects[x-1][1]);
memset(pre,-1,sizeof(pre));
dp[0]=0;
goal=(1<<n)-1;
for (t=1;t<=goal;t++)
for (i=0;i<n;i++)
if (t & (1<<i))
{
temp=arc[0][i+1]<<1;
p=(t^(1<<i));
if (pre[t]==-1 || dp[t]>dp[p]+temp)
dp[t]=dp[p]+temp,pre[t]=p;
for (x=i+1;x<n;x++)
if (t & (1<<x))
{
temp=arc[0][i+1]+arc[0][x+1]+arc[i+1][x+1];
p=t^(1<<i)^(1<<x);
if (pre[t]==-1 || dp[t]>dp[p]+temp)
dp[t]=dp[p]+temp,pre[t]=p;
}
break; //关键
}
x=goal;
printf("%d\n",dp[x]);
while (x)
{
printf("0 ");
t=pre[x];
for (i=0;i<n;i++)
if ((x & (1<<i)) && !(t & (1<<i)))
printf("%d ",i+1);
x=t;
}
printf("0\n");
}
return 0;
}
/*
0 0
24
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 0
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 0
3 1
3 2
3 3
3 4
*/