集训作业 洛谷P1433 吃奶酪
2024-09-04 00:32:56
嗯?这题竟然是个绿题。
这个题真的不难,不要被他的难度吓到,我们只是不会计算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;
}
这个题没什么可讲的,一个纯洁的深搜就可以解决了。
最新文章
- 讲讲Android事件拦截机制
- hdu分类 Dynamic Programming(这是一场漫长的旅途)
- SQLite如何测试
- Visual Studio2013(Update4)无法生成依赖项关系图解决方案
- Atitit.js图表控件总结
- CodeForces 163A Substring and Subsequence dp
- Dictionary<;Key,Value>;的用法
- Oracle 获取表结构信息
- JavaScript数组遍历(迭代)方法 8种
- NSTimer、CADisplayLink 内存泄漏
- Mysql隔离级别,锁与MVCC
- vsftp 的安装及配置
- ubuntu学习笔记
- call 和 apply 的区别
- RocketMQ系列实战
- nginx安装ngx_lua_waf防护
- 【转】Python数据类型之“序列概述与基本序列类型(Basic Sequences)”
- PL/SQL学习笔记之触发器
- 洛谷P3721 单旋
- 产品排序(2015 年北大自招夏令营) (与栈相关的区间DP)
热门文章
- cb14a_c++_顺序容器的操作7_赋值与交换(swap)_vector转list
- async/await剖析
- 大文件上传、断点续传、秒传、beego、vue
- shell 脚本操作informix数据库
- redis基础二----操作hash
- 前端日常工作中常用开发小技巧 ---JavaScript
- (八十九)c#Winform自定义控件-自定义滚动条(treeview、panel、datagridview、listbox、listview、textbox)
- 修改CentOS7登录欢迎界面信息
- Netty源码学习系列之5-NioEventLoop的run方法
- Java基础-线程与并发1