P1433 【吃奶酪】 · znzryb
## 思路讲解
状压dp的整体思想就是将状态用一个数表示出来，进而方便状态转移。
```cpp
double dp[25][33000]; // 状压dp数组
// 当前点 状态
```
那么问题就来了，怎么进行状态转移（在这题里）？
```cpp
for(int i=1;i<=(1<<n)-1;++i){ // 枚举所有状态
for(int j=1;j<=n;++j){ // 枚举当前点
if((i & (1<<j-1))==0) // 说明当前点没走过,这是不合法的
// 该操作相当于只保留了i的第j位二进制数（0，1）
continue;
for(int k=1;k<=n;++k){ // 枚举要去的点
if((i & (1<<k-1))==0){
int status=(1<<k-1)+i;
dp[k][status]=min(dp[j][i]+Dis[j][k],dp[k][status]);
}
}
}
}
```
## AC代码
[https://www.luogu.com.cn/record/191940029](https://www.luogu.com.cn/record/191940029)
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
double Loc[25][3],Dis[25][25];
double dp[25][33000]; // 状压dp数组
// 当前点 状态
// 2**15==32768,也就是用二进制下的15位数可以搞定
// 当然第十五位二进制下表示2**14
// 一共约33000种状态
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;++i){
cin>>Loc[i][0]>>Loc[i][1];
}
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){ // 原点到不同点之间的距离也需要统计
if(i==j)
continue;
double x1=Loc[i][0],y1=Loc[i][1];
double x2=Loc[j][0],y2=Loc[j][1];
Dis[i][j]=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
}
memset(dp, 127, sizeof(dp)); // 初始化dp为极大值
for(int i=1;i<=n;++i) // 初始化原点到各个点的值
dp[i][1<<(i-1)]=Dis[0][i];
for(int i=1;i<=(1<<n)-1;++i){ // 枚举所有状态
for(int j=1;j<=n;++j){ // 枚举当前点
if((i & (1<<j-1))==0) // 说明当前点没走过,这是不合法的
// 该操作相当于只保留了i的第j位二进制数（0，1）
continue;
for(int k=1;k<=n;++k){ // 枚举要去的点
if((i & (1<<k-1))==0){
int status=(1<<k-1)+i;
dp[k][status]=min(dp[j][i]+Dis[j][k],
dp[k][status]);
}
}
}
}
double ans=1e17;
for(int i=1;i<=n;++i){
int status=(1<<n)-1;
ans=min(dp[i][status],ans);
}
cout<<setprecision(2)<<fixed<<ans<<endl;
}
// AC https://www.luogu.com.cn/record/191940029
```
## 心路历程（WA，TLE，MLE……）
前面status和点的idx位置放反了，导致了RE