P1433 吃奶酪 状态压缩dp 时间复杂度O（n^2*2^n）

题目链接

---

#include<stdio.h>
#include<math.h>
#include<string.h>
int n;
double x[20],y[20],id[20],dis[20][20],f[20][35000],ans;//f代表当前点为i时，且途径的点集合为j时的总距离的最小值； 
double jishuan(double x11,double y11,double x22,double y22){
	return sqrt(pow(x11-x22,2)+pow(y11-y22,2));
}
double min(double x11,double y11){
	if(x11<=y11){
		return x11;
	}
	else{
		return y11;
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lf%lf",&x[i],&y[i]);
	} 
	for(int i=0;i<n;i++){//第i个点 
		for(int j=i+1;j<=n;j++){//下一个点 
			 dis[i][j]=jishuan(x[i],y[i],x[j],y[j]);
			dis[j][i]=dis[i][j];
		}
	}
	memset(f,127,sizeof(f));//memset(a,127,sizeof(a));即得到无穷大memset(a,128,sizeof(a));即得到无穷小，与上述的值互为相反数。
	for(int i=1;i<=n;i++){
		f[i][1<<(i-1)]=dis[i][0];
	} 
	for(int i=1;i<(1<<n);i++){//途径点的集合 
		for(int j=1;j<=n;j++){//当前的点 
			if(i&(1<<(j-1))){//当途径点的集合含有当前点的时候 
				for(int z=1;z<=n;z++){//前一个点 
					if(i&(1<<(z-1))&&z!=j){
						f[j][i]=min(f[j][i],f[z][i-(1<<(j-1))]+dis[z][j]);
					}
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(i==1){
			ans=f[i][(1<<n)-1];
		}
		else{
			if(f[i][(1<<n)-1]<ans){
					ans=f[i][(1<<n)-1];
			}
		}
	}
	printf("%.2lf",ans);
	return 0;
}

---

前言：

本题的难点在于dp的状态保存与转移，传统dp内存会炸以及暴力搜索会被n=15即（15！>>1e8）而卡住，同时本题贪心不可取，可能有局部贪心可以优化但是本人还没发现局部贪心，由于状态压缩dp的时间复杂度有点高，在1e8以内我计算发现n在21以内都没问题所有本题就采用状态压缩来写。

---

思路：

将数的二进制每一位上的一代表该下标的点以及走过，比如4（10）->0000 0100 (2)代表走过了第3个点。而 1011 0100代表走过3，5，6，8这4个点。
dp[i][j]代表当当前点是第i个点的时候，j是这个途径点的集合的2进制的10进制数，走过所有途径点的最小值。
所有状态转移方程就是dp[i][j]=min(dp[i][j],dp[z][j-(1<<(i-1))]+dis[i][z]);