题解 P1433 【吃奶酪】

· · 题解

updated 2020.10.10：更正了文中状态转移方程的错误

本题用到的知识点：

状压DP

状压 dp 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 - OI wiki

状态压缩的思想是用二进制来表示状态。用一个整数的二进制形式的每一个二进制位 0 或 1 表示一个状态。

本题会涉及到部分位运算的知识

本题是一道比较基础的状压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} 中的最小值就是最终的答案了。

代码如下

#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);
}