【每日一题】洛谷 p1433 吃奶酪 状压dp

- [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433)

换一种类型，这次求长度最小值，（n<15)接着状压

题目：房间里放着 nn 块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在 (0,0)(0,0) 点处。

梳理状态：1吃了几个，2吃了哪几个 （dp[i个][吃完第i个是什么状态]）

写出递推式

dp[j][i]=min(dp[j][i],dp[p][i-(1<<(j-1))]+a[p][j]);
//当前距离  p：上一个是哪个点  i-(1<<(j-1))：上一个状态 a[p][j]距离

思路：先求出任意两点间距离，按照状态选择结束启示两点进行遍历。

for(int i=1;i<(1< 
别忘了初始化，最后给出ac代码
 
#include
using namespace std;
double a[20][20];
double vx[20],vy[20];
double dp[16][20005];
double dis(int p1,int p2){
	return sqrt((vx[p1]-vx[p2])*(vx[p1]-vx[p2])+(vy[p1]-vy[p2])*(vy[p1]-vy[p2]));
}
int main(){
	double ans=1000000005;//这个有点呆qwq
	int n;
	cin>>n;
	memset(dp,127,sizeof(dp));//初始化最大值
	for(int i=1;i<=n;i++){
		cin>>vx[i];
		cin>>vy[i];
	}
	
	for(int i=0;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			a[i][j]=dis(i,j);
			a[j][i]=a[i][j];
		}
	}
	
	for(int i=1;i<=n;i++){
		dp[i][(1<<(i-1))]=a[0][i];//先走第一步
	}
	
	for(int i=1;i<(1<