COdevs 2823 锁妖塔
2823 锁妖塔
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
琐妖塔会在一会儿后倒塌。大量妖魔涌出塔去,塔内的楼梯都挤满了人(哦,错了,是妖),(那他们怎么不飞下去--)要求是,景天一行一定要下塔,琐妖塔一共N层,但是他突然大发慈悲,觉得妖怪是无辜,所以他不想踩死这些妖魔,所以他的速度最多比妖怪速度大K(否则会踩死妖怪的),并且速度不能比妖怪们慢,否则会被踩死。琐妖塔一共有N层,并且每层怪物逃跑的速度都不相同,景天每下一层,可以选择将他的速度加快一个单位或者减慢一个单位或者保持原来的速度不变。并且他下每一层的速度之和除以(N-1)要尽量大。当然跑下楼时他一定要活着。
现在景天刚拿到镇妖剑,头有点热,不能思考了,请你编个程序帮帮他吧!
提示:1楼不需要再下了,N层楼只需要下N-1层。并且在第N层楼到N-1层时必须为初始速度。
第一行,三个整数N,V(初始速度),K(最多比其他妖快的速度值)
第二行,N-1个整数,分别代表从第二层到第N层的妖怪的速度
其中2〈=N〈=100,0〈=K〈=100,1〈=V〈=100。
若能下楼,输出速度之和除以(N-1),保留两位小数。
若不能,那就仰天大吼一声,输出“REN JIU SHI BU NENG REN CI!”(不含引号)
Input1
3 3 2
2 2
Input2
3 3 0
2 2
Output1
3.50
Output2
REN JIU SHI BU NENG REN CI!
RT
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef double db;
int n,v,k;
struct meico{
int v;
int ceng;
int tot;
};
db ans=;
const int maxn=;
int spd[maxn],cg[]={,,,-},maxs[maxn];
bool flag;
void dfs(int vv,int ceng,int tot){
if(ceng==){
flag=;ans=max(ans,(db)((db)(tot)/db(n-)));
return ;
}
if(flag) return;
for(int i=;i<=;i++){
int v1=vv+cg[i];
if(vv>=spd[ceng-]&&(vv-spd[ceng-])<=k){
if(ceng-!=)
dfs(v1,ceng-,tot+v1);
else dfs(v1,ceng-,tot);
}
}
}
int main()
{
scanf("%d%d%d",&n,&v,&k);
for(int i=;i<n;i++)
scanf("%d",&spd[i]); if(v>=spd[n-]&&v-spd[n-]<=k){
dfs(v,n,v);
if(ans!=)
printf("%.2lf\n",ans);
else printf("REN JIU SHI BU NENG REN CI!");
}
else{
printf("REN JIU SHI BU NENG REN CI!");
return ;
} return ;
}
刚开始一见这题,仙剑奇侠传!!!!!梦幻西游!!!!!!!鬼吹灯!!!!!!!!
由于题目下面写的宽搜,于是我一开始就打了宽搜….结果3^100直接MLE。
所以用深搜。
这题我们枚举下楼的情况时,把速度+1放在最前面,这样能减掉不少枝,当搜到第一层的时候,更新答案,然后如果后面的最优答案小于当前最优答案,就减掉。
最新文章
- MediaElement.js之浏览器跨域请求视频播放
- ArithUtil工具类 : 精确计算各种运算
- 同一web系统,不同端口的跨域问题
- C#XmlHelper操作Xml文档的帮助类
- HDOJ 1874
- Unity3D之Mecanim动画系统学习笔记(六):使用脚本控制动画
- NSURLConnection、NSURLSession
- Sample Ant Build File - WAR--reference
- IP V4地址分类
- sql 查找数据库中某字符串所在的表及字段
- hdu 1019 n个数的最小公倍数
- (转载)Setup Factory 会话变量
- 2014年国内经常使用移动client推送服务介绍和比較
- C++习题 商品销售
- webpack的四个核心概念介绍
- 201521123048 《Java程序设计》第7周学习总结
- PuppeteerSharp: 更友好的 Headless Chrome C# API
- 我的第一个python web开发框架(41)——总结
- [Swift]LeetCode277. 寻找名人 $ Find the Celebrity
- hibernate基本的配置与验证
热门文章
- Caused by: java.lang.ClassNotFoundException: org.springframework.boot.system.JavaVersion
- scanf(";%s";,s)与gets(s)
- sort函数的使用
- mysql的备份与恢复详解
- 第三届上海市大学生网络安全大赛wp&;学习
- tp5 -- 微信公众号支付
- Bootstrap历练实例:块级按钮
- angular-file-upload 在IE下使用的坑
- 【二分 贪心】bzoj3477: [Usaco2014 Mar]Sabotage
- Codeforces Round #477滚粗记&;&;祭第一次div2场