题解 P1433 【吃奶酪】
其实本题不用状压也能过的。。。
本题看上去就是一个普通的搜索，不过需要一些（玄学）技巧
但是还是要用到状压（会卡一个点）
不过相对真·状压来说比较好理解
代码：
#include<stdio.h>
#include<math.h>
int n;
double a[20],b[20],dp[65000][20];
bool v[20];
double ans=1e9;
double dis(int x,int y){
sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));//距离公式
}
void dfs(int t,int now,double s,int b){
if(s>ans) return; //剪枝
if(t==n){
ans=ans<s?ans:s;
return;
}
for(register int i=1;i<=n;i++){
if(!v[i]){
int p=b+(1<<(i-1));//状压存状态
if(dp[p][i]!=0&&dp[p][i]<=s+dis(now,i)) continue;//判断条件+优化
v[i]=1;
dp[p][i]=s+dis(now,i);
dfs(t+1,i,dp[p][i],p);
v[i]=0;//回溯
}
}
}
main(){
scanf("%d",&n);
for(register int i=1;i<=n;i++)
scanf("%lf%lf",&a[i],&b[i]);
dfs(0,0,0,0);
printf("%.2lf\n",ans);
return 0;
}