P1433-吃奶酪

太过爱你忘了你带给我的痛 2023-06-01 08:49 32阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     4 typedef double db;
     5 const int maxn = 20;
     6 db rnt = 1<<30;
     7 int n;
     8 double x[maxn],y[maxn],dis[maxn][maxn];
     9 
    10 double dfs(int s,db sum,int cur)
    11 {
    12     if(sum>rnt)
    13         return 1<<30;
    14     if(s==(1<<(n+1))-1)
    15         rnt = min(rnt,sum);
    16     
    17     _for(i,0,n+1)
    18         if(!((1<<i)&s))
    19         {
    20             s |= 1<<i;
    21             dfs(s,sum+dis[cur][n-i],n-i);
    22             s ^= 1<<i;
    23         }
    24 }
    25 
    26 int main()
    27 {
    28     scanf("%d",&n);
    29     _for(i,1,n+1)
    30         scanf("%lf%lf",&x[i],&y[i]);
    31     x[0]=0,y[0]=0;
    32     _for(i,0,n+1)
    33         _for(j,0,n+1)
    34             dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    35     
    36     dfs(1<<n,0.0,0);
    37     printf("%0.2f\n",rnt);
    38     return 0;
    39 }

转载于:https://www.cnblogs.com/Asurudo/p/11250199.html

发表评论取消回复

表情：

评论列表（有 0 条评论，32人围观）

还没有评论，来说两句吧...

相关阅读

相关【记忆化搜索】老鼠吃奶酪

woc，这种DP用记忆化搜索就很好写啊，老师之前说要建图什么的让我一直望而生畏，实际上记忆化一下就好了啊啊啊啊啊啊如果图中不存在环而是个DAG就可以用记忆化搜索写，否则就得

小咪咪/ 2024年03月26日 16:19/ 0 赞/ 78 阅读

相关 P1508-Likecloud-吃、吃、吃

1 include <bits/stdc++.h> 2 define maxn 13003 3 define _for(i,a,b) for(int

た入场券/ 2023年06月01日 08:51/ 0 赞/ 35 阅读

相关 P1433-吃奶酪

1 include <bits/stdc++.h> 2 using namespace std; 3 define _for(i,a,b) for(

太过爱你忘了你带给我的痛/ 2023年06月01日 08:49/ 0 赞/ 32 阅读

相关 P3958 [NOIP2017 提高组] 奶酪——广搜

看原题：[P3958 \[NOIP2017 提高组\] 奶酪][P3958 _NOIP2017 _] 题目描述现有一块大奶酪，它的高度为 h，它的长度和宽度我们可以

绝地灬酷狼/ 2023年01月14日 14:00/ 0 赞/ 172 阅读

相关洛谷P1433 吃奶酪--Java解法(货郎担问题)

洛谷P1433 吃奶酪–Java解法(货郎担问题) [题目链接][Link 1] 解决思想本题目是一个典型的货郎担问题,即从(0,0)点出发,所有点仅经过依次(

绝地灬酷狼/ 2022年10月30日 01:28/ 0 赞/ 197 阅读

相关洛谷P1433 吃奶酪

题目描述房间里放着n块奶酪。一只小老鼠要把它们都吃掉，问至少要跑多少距离？老鼠一开始在(0,0)点处。输入输出格式输入格式：第一行一个数n (n<

ゝ一世哀愁。/ 2022年05月30日 03:05/ 0 赞/ 206 阅读

相关洛谷 P1508 Likecloud-吃、吃、吃

题目背景问世间，青春期为何物？答曰：“甲亢，甲亢，再甲亢；挨饿，挨饿，再挨饿！” 题目描述正处在某一特定时期之中的李大水牛由于消化系统比较发达，最近一直处

落日映苍穹つ/ 2022年05月27日 03:15/ 0 赞/ 208 阅读

相关 P3958 奶酪

原题链接 [https://www.luogu.org/problemnew/show/P3958][https_www.luogu.org_problemnew_show_

快来打我*/ 2021年12月05日 04:53/ 0 赞/ 277 阅读

相关【洛谷p3958】奶酪

[奶酪【题目链接】][Link 1] 题前废话不知道说啥了啊qwq（越来越沉默寡言） ![1605606-20190705112254691-609612393.png][

矫情吗；*/ 2021年11月14日 11:10/ 0 赞/ 468 阅读

相关【阿里云在线编程】 49.吃奶酪二分法

<table> <tbody> <tr> <td><font>题目</font></td> </tr> </tbody> </table>

迷南。/ 2021年06月10日 20:38/ 0 赞/ 337 阅读