吃奶酪

快快做题 · 2019-01-05 11:06:18 · 题解

博客阅读效果更佳

P1433吃奶酪题解

做法

状压dp(本篇重点）
暴搜+最优化剪枝（待实现）
玄学算法（见其他题解）

前置

状压dp，全称状态压缩dp，是一种在数据范围不大（n<=20左右）的情况下，代替暴搜的常用方法
状态常以二进制形式表示，从左往右第k位表示第k个元素的选择情况，0表示未被选择，1表示已选

例如二进制下110101，表示第1、3、5、6个元素已被选择
因为涉及二进制，所以简单的位运算必须掌握
1.对位判断：例如第k位为0 ((1<<(k-1))&s)==0
2.枚举子集
```
for(int S1=S;S1!=0;S1=(S1-1)&S){
S2=S^S1;
}
```
3.and so on

为了方便调试，学会十进制转二进制也很有必要

int shizhuaner(int dec){
int result = 0,temp = dec,j = 1;
while(temp){
    result = result + j*(temp%2);
    temp = temp/2;
    j = j*10;
}
return result;
}

本题的错误做法

由noip2016愤怒的小鸟而来，那是我用状压的第一道题，大家也可以先做该题以入门状压
看了上面那道题，自然而然地想到用s表示哪些点被选择，而f[s1]可以推出加入任意一个未到达的点k后的状态s2，f[s1]=f[s2]+len(k,s1中所有已到的点距离最小值）

      int main()
      {
          scanf("%d\n",&n);
          for(ri i=1;i<=(1<<n);i++)f[i]=inf+1;
          for(ri i=1;i<=n;i++){
              scanf("%lf%lf",&x[i],&y[i]);
              f[(1<<(i-1))]=jl(0,0,x[i],y[i]);//边界  
          }
          for(ri i=1;i<n;i++){
              for(ri j=i+1;j<=n;j++)
              len[i][j]=len[j][i]=jl(x[i],y[i],x[j],y[j]);
          }
          f[0]=0;
          for(ri s=1;s<(1<<n);s++){
              if(f[s]>=inf)continue;
              cnt=0;
              for(ri k=0;k<n;k++){//找到s中所有已经到达的点 ，并存起来 
                  if(((1<<k)&s)!=0){
                      que[++cnt]=k+1;
                  }
              }
              for(ri k=0;k<n;k++){
                  if(((1<<k)&s)==0){//找到s中所有未到的点 
                      tmp=inf;
                      for(ri l=1;l<=cnt;l++){
                          tmp=min(tmp,len[que[l]][k+1]);//找一条由s中的点到新点的最短路 
                      }
                      f[(1<<k)|s]=min(f[(1<<k)|s],f[s]+tmp);
                  }
              }
          }
          printf("%.2lf",f[(1<<n)-1]);
          return 0;
      }

很快打完了，乘兴而来........败兴而归
为什么呢？我的想法这么优秀，这题又是普及-能难到哪去？

正确做法
先来看一幅图
如果只看4、 5 、6 三个点，f[ ]为几呢？我的程序给的是7，标准程序是7.41，难道我们的做法比题解还优？？？
我们动手试一下，先从(0,0)到（3，-4），距离为5，再走4->5, 4->6,各为1,于是答案为7
想一下，我们到了4后，先从4走到5，后从4走到6，为什么小老鼠已经到了5，又回到了4呢？
原来我们的思路出问题了，在新的距离选取中不能找最短路，而要找从当前点到新点的距离。
现在的目标是存储当前点，于是我们用F[ 当前点i ] [ 当前状态 ] 完整地表示一个状态，转移方程也很好写，具体见代码。~~其实是我不会发公式~~

      #include <bits/stdc++.h>
      #define ri register int
      using namespace std;

      int i,j,k,n,que[17],cnt,p;
      double x[17],y[17];
      double tmp,ans;
      double len[17][17],f[17][100000];

      double jl(double x1,double y1,double x2,double y2)
      {
          return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
      }
      int dect(int dec){// 十进制转二进制，便于调试 
          int result = 0,temp = dec,j = 1;
          while(temp){
              result = result + j*(temp%2);
              temp = temp/2;
              j = j*10;
          }
          return result;
      }

      int main()
      {
          memset(f,127,sizeof(f));//double无穷大赋值方式 
          scanf("%d\n",&n);
          for(ri i=1;i<=n;i++){
              scanf("%lf%lf",&x[i],&y[i]);//注意是实数读入 
              f[i][(1<<(i-1))]=jl(0,0,x[i],y[i]);//边界条件 
          }
          for(ri i=1;i<n;i++){
              for(ri j=i+1;j<=n;j++)
              len[i][j]=len[j][i]=jl(x[i],y[i],x[j],y[j]);
          }
          for(ri s=1;s<(1<<n);s++){
              cnt=0;
              for(ri k=0;k<n;k++){//注意从0开始，所以下面的转移方程中要加一 
                  if(((1<<k)&s)==0)que[++cnt]=k;
              }//求出所有未到达的点 
              for(ri i=1;i<=n;i++){
                  if(abs(f[i][s]-f[0][0])<0.0000001) continue;//浮点数相等表示法 
                  for(ri l=1;l<=cnt;l++){
                      f[que[l]+1][s|1<<(que[l])]=min(f[que[l]+1][s|1<<(que[l])],f[i][s]+len[que[l]+1][i]);
                  }
              } 
          }
          ans=f[0][0];//赋予一个无穷大初值 
          for(ri i=1;i<=n;i++)ans=min(ans,f[i][(1<<n)-1]);
          printf("%.2lf",ans);
          return 0;
      }

小细节

memset(f,127,sizeof(f));//double无穷大赋值方式

十进制转二进制，便于调试
读入坐标都是实数

最后宣传一波博客~~，虽然目前什么都没有~~

吃奶酪

P1433吃奶酪题解

做法

前置

本题的错误做法

正确做法

小细节