题解 P1433 【吃奶酪】

#### updated 2020.10.10：更正了文中状态转移方程的错误 ------------ 本题用到的知识点： ## 状压DP > 状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 - [OI wiki](https://oi-wiki.org//dp/state/) **状态压缩**的思想是用二进制来表示状态。用一个整数的二进制形式的每一个二进制位 $0$ 或 $1$ 表示一个状态。 ------------ 本题会涉及到部分[位运算](https://oi-wiki.org//math/bit/)的知识 本题是一道比较基础的状压DP题目。 状压DP的时间复杂度为 $O(n^2 2^n)$，通常只能通过 $N \leq 21$ 的数据范围，本题数据范围为 $N \leq 15$ 因此可以使用状压DP。 #### 思路 坐标可能为实数，因此要用double类型存储。 定义一个数组 $F_{i,j}$，表示老鼠走到第 $i$ 个奶酪，且走过的二进制状态为 $j$ 时，最短的距离。 举例来说，可以使用二进制 $10100110$ 来表示已经走过第 $2$、$3$、$6$、$8$ 个奶酪，此时 $j$ 的值为 $166$。需要注意的是，第 $i$ 个状态是从低位向高位的第i位。 在更新 $F$ 数组状态时会用到两点间的距离，使用两点间距离公式计算： $a = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ 首先要将 $F$ 数组进行初始化为极大值，可以使用```memset(F,127,sizeof(F));```来为浮点数赋极大值 因为到达第 $i$ 块奶酪，且只经过过第 $i$ 块奶酪的距离即为第i块奶酪与坐标原点的距离。因此要初始化```F[i][(1<<(i-1))]=a[0][i];```。 接下来是三层循环，分别枚举所有可能的二进制状态、当前点所在的位置和能在当前状态下到达当前点的位置。 在第二层循环中要判断一下 $i$ 在当前二进制状态下是否已走过，如果根本没走过则不需要进行接下来的计算，直接continue就可以。 在第三层运算中同样要判断当前点是否已走过，且当前点不与 $i$ 点相同。 接下来就可以转移状态了： 设此时二进制状态为 $k$，终点为 $i$，起点为 $j$，可得状态转移方程：$F_{i,k}=\min(F_{i,k},F_{j,k-{2^{i-1}}} +A_{i,j})$。$F_{j,k-{2^{i-1}}}$ 为在 $j$ 点且没有走过 $i$ 点的最短距离， $A_{i,j}$ 是从 $i$ 到 $j$ 的距离。 最后，找出 $F_{i,2^N-1}$ 中的最小值就是最终的答案了。 #### 代码如下 ```cpp #include <cstdio> #include <cstring> #include <cmath> #define min(a,b) (((a)<(b))?(a):(b)) //洛谷 P1433 吃奶酪 状压DP double a[20][20];//预处理，从第i块到第j块的距离，使用两点之间距离公式 double x[20],y[20];//每块奶酪的横、纵坐标 double F[18][34000];//状压DP数组 在第i个点上，走过的二进制状态的十进制表达为j时，最短的距离 int N; double distance(int v,int w)//计算第v个和第w个奶酪之间的距离 { return sqrt((x[v]-x[w])*(x[v]-x[w])+(y[v]-y[w])*(y[v]-y[w]));//两点间距离公式 } int main() { int i,j,k; double ans; memset(F,127,sizeof(F));//这样可以给浮点数赋值无穷大 ans=F[0][0]; scanf("%d",&N); for(i=1;i<=N;i++) { scanf("%lf%lf",&x[i],&y[i]);//数据读入 } x[0]=0;y[0]=0; for(i=0;i<=N;i++) { for(j=i+1;j<=N;j++) { a[i][j]=distance(i,j);//初始化距离数组 a[j][i]=a[i][j]; } } for(i=1;i<=N;i++)//初始化 { F[i][(1<<(i-1))]=a[0][i];//在i点上且只有经过i点时距离是原点到i点的距离 } for(k=1;k<(1<<N);k++)//枚举所有二进制的状态 { for(i=1;i<=N;i++) { if((k&(1<<(i-1)))==0) continue;//i的位置没被走过，所以不需要再继续计算了 for(j=1;j<=N;j++) { if(i==j) continue;//同一个点不需要再计算 if((k&(1<<(j-1)))==0) continue;//j的位置没走过 F[i][k]=min(F[i][k],F[j][k-(1<<(i-1))]+a[i][j]); } } } for(i=1;i<=N;i++) { ans=min(ans,F[i][(1<<N)-1]); } printf("%.2f\n",ans); } ```