洛谷P1433 吃奶酪
题目大意
房间里放着 n 块奶酪，一只小老鼠从原点 (0,0) 出发，要吃掉所有奶酪，求最少需要跑多少距离。
数据范围： 1≤n≤15，坐标绝对值不超过 200，小数点后最多三位。
分析
个人认为本题是状压dp的入门经典题目，巧妙地引入二进制这个状态压缩方式。
n 较小，但直接枚举所有 n!种顺序不可行（15!15! 极大）。
注意每个奶酪只有“被吃过”和“未吃过”两种状态，且当前所在位置影响后续距离，考虑状态压缩动态规划。
用二进制数表示哪些奶酪已经被访问，再记录当前停留的奶酪编号，即可表示一个完整状态。
Solution
标签： 状压DP
1. 状态定义
定义 dp[mask][i]表示：
当前已经吃过的奶酪集合为 mask（二进制第 j位为 1 表示第 j 块奶酪已被吃）；
当前停留在第 i 块奶酪（i 从 0 到 n）；
值为从原点出发，吃完 maskmask 中的奶酪且最后在 i的最短距离。
2. 状态转移
初始化
一开始只有原点被访问，停留在原点：
dp[1][0]=0。
其中 11 表示二进制只有第 0 位为 1。
距离预处理
预先计算任意两点之间的欧几里得距离：
dist[i][j] = sqrt((x_i - x_j) * (x_i - x_j) + (y_i - y_j) * (y_i - y_j))
对于当前状态 dp[mask][i]，枚举下一个未访问的点 j（即 mask 中第 j 位为 0）：
dp[mask | (1 << j)][j] = min(dp[mask | (1 << j)][j], dp[mask][i] + dist[i][j])
注意当前状态一个有2的n次方种，因此考虑完了所有的情况，同时注意，需要用continue避免一些不可能发生的情况。
最终答案
所有奶酪都被吃，即 mask 包含所有点（原点 + 所有奶酪），二进制全 1：
full = (1 << (n+1)) - 1
取最后停留在任意点的最小值：
ans = min(dp[full][i])，其中 i 从 0 到 n
3. 时间复杂度
状态总数：2^(n+1) × (n+1)，当 n=15 时约为 65536 × 16 = 1,048,576。
每个状态需枚举 n+1 个可能的下一结点，总操作数 O(2^(n+1) × (n+1)^2) ≈ 65536 × 256 = 1.68 × 10^7，完全可行。
注意浮点数精度，输出保留两位小数。
4. 代码实现要点
将原点作为第 0 个点存入坐标数组，奶酪依次存入 1..n
预处理所有点对距离存入 dist 矩阵
dp 数组大小 [1 << (n+1)][n+1]，初始化为大数（如 1e9），dp[1][0] = 0
三重循环：
外层枚举状态 state
中层枚举当前点 i（要求 state 包含 i）
内层枚举下一未访问点 j（要求 state 不包含 j）
更新 dp[state | (1 << j)][j]
最终在 dp[(1<<(n+1))-1][i] 中取最小值输出
下面是代码
//通过二进制数显示已经访问的城市
//由于所有的情况都需要遍历，所有先需要一个循环，遍历二进制的所有情况
//需要第二个，遍历每个二进制数组中的所站城市
//需要第三个循环，遍历能去的城市
//因为还需要比较，所以还得把初始量都设为最大
//然后遇到所有的遍历情况都要考虑剪枝
//这里剪的是无法到达的，当前城市无法去当前城市的
include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = INT_MAX / 2;
vector<vector
double twop(double x1, double y1, double x2, double y2){
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2)*(y1 - y2));
}
//先写一个距离数组
void f(vector<vector
ll len = nn.size();//长,同时也是宽
dist.resize(len,vector
for(int i = 0; i < len; i++){double xi = nn[i][0];double yi = nn[i][1];for(int j = 0; j < len; j++){double xj = nn[j][0];double yj = nn[j][1];dist[i][j] = twop(xi,yi,xj,yj);}
}
}
double tap(){
//这里需要三个遍历，想不出来可以先找三个遍历的条件
ll n = dist.size();
ll totalstate = (1 << n) - 1;
vector<vector
dp[1][0] = 0;
for(int state = 1; state < totalstate; state++){
for(int i = 0; i < n; i++){
//当前站着的城市没有亮，也就是没有这个城市
if((state & 1 << i) == 0){
continue;
}
if(dp[state][i] == 1e9){
continue;
}
for(int j = 0; j < n; j++){
//检查过当前站的城市是否亮，是否不能站当前城市，就剩下去的城市不能是已经去过的了
if(state & (1 << j)){
continue;
}
ll newState = state | (1 << j);//打开开关
double newCoat = dp[state][i] + dist[i][j];
if(newCoat < dp[newState][j]){dp[newState][j] = newCoat;}}}
}
double res = 1e9;
for(int i = 0; i < n; i++){res = min(res,dp[totalstate][i]);
}
return res;
}
int main(){
ll n;
cin >> n;
vector<vector<double> > coordinate(n + 1,vector<double> (2,0));//坐标的数组
coordinate[0][0] = 0;
coordinate[0][1] = 0;
for(int i = 1; i < n + 1; i++){cin >> coordinate[i][0];cin >> coordinate[i][1];
}
f(coordinate);
double ans = tap();cout << fixed << setprecision(2) << ans << endl;
return 0;
}