13的博客

13的博客

题解 P1433 【吃奶酪】

posted on 2020-07-19 21:59:55 | under 题解 |

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