嗯?这题竟然是个绿题。

这个题真的不难,不要被他的难度吓到,我们只是不会计算2点之间的距离,他还给出了公式,这个就有点……

我们直接套公式去求出需要的值,然后普通的搜索就可以了。

这个题我用的深搜,因为广搜没什么意义。

#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
struct z
{
double x,y;
}g[20];
using namespace std;
double s[20][20];
int n,bj[20];
double maxx=9999999.0;
int dfs(int bs,int xz,double jl)//3个参数分别是吃了几个奶酪,现在在第几个奶酪的位置和一共走了多远。
{
if(jl>=maxx)//现在比最远的一次都远了,再走会更远。
{
return maxx;
}
if(bs==n)//全都吃完了,比较一下哪个大,返回
{
maxx=min(maxx,jl);
return maxx;
}
for(int i=1;i<=n;i++)
{
if(bj[i]==0)//bj表示这个奶酪吃过没有
{
bj[i]=1;//现在吃过了
dfs(bs+1,i,jl+s[xz][i]);//下一层循环。
bj[i]=0;//这次吃它的情况全试过了,试试这次不吃。
}
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)//正常的输入
{
cin>>g[i].x>>g[i].y;
}
g[0].x=0;
g[0].y=0;
for(int i=0;i<=n;i++)
{
for(int j=0;j<=n;j++)//s[i][j]的意思是第i块奶酪到第j块奶酪的距离
{
s[i][j]=sqrt((g[i].x-g[j].x)*(g[i].x-g[j].x)+(g[i].y-g[j].y)*(g[i].y-g[j].y));//公式套上。
}
}
dfs(0,0,0.0);//开始搜索
printf("%.2f",maxx);//保留2位小数。%.2f
return 0;
}

这个题没什么可讲的,一个纯洁的深搜就可以解决了。

最新文章

  1. 讲讲Android事件拦截机制
  2. hdu分类 Dynamic Programming(这是一场漫长的旅途)
  3. SQLite如何测试
  4. Visual Studio2013(Update4)无法生成依赖项关系图解决方案
  5. Atitit.js图表控件总结
  6. CodeForces 163A Substring and Subsequence dp
  7. Dictionary&lt;Key,Value&gt;的用法
  8. Oracle 获取表结构信息
  9. JavaScript数组遍历(迭代)方法 8种
  10. NSTimer、CADisplayLink 内存泄漏
  11. Mysql隔离级别,锁与MVCC
  12. vsftp 的安装及配置
  13. ubuntu学习笔记
  14. call 和 apply 的区别
  15. RocketMQ系列实战
  16. nginx安装ngx_lua_waf防护
  17. 【转】Python数据类型之“序列概述与基本序列类型(Basic Sequences)”
  18. PL/SQL学习笔记之触发器
  19. 洛谷P3721 单旋
  20. 产品排序(2015 年北大自招夏令营) (与栈相关的区间DP)

热门文章

  1. cb14a_c++_顺序容器的操作7_赋值与交换(swap)_vector转list
  2. async/await剖析
  3. 大文件上传、断点续传、秒传、beego、vue
  4. shell 脚本操作informix数据库
  5. redis基础二----操作hash
  6. 前端日常工作中常用开发小技巧 ---JavaScript
  7. (八十九)c#Winform自定义控件-自定义滚动条(treeview、panel、datagridview、listbox、listview、textbox)
  8. 修改CentOS7登录欢迎界面信息
  9. Netty源码学习系列之5-NioEventLoop的run方法
  10. Java基础-线程与并发1