#10 [AH2017/HNOI2017]大佬
2024-10-13 18:02:30
题解:
题意看上去挺复杂的
分析一下就能发现自己的自信是没啥用的
只要随便dp一下看看最多能有多少天不使用增加自信
然后问题就变成了
求C1+C2+k=C
然后发现C有10^8
显然枚举C1是不行的了
那么考虑到满足条件的C1,C2应该不会太多
可以考虑先把它们搞出来
这个只需要hash+bfs就可以了
令f[i][j]表示当前生成了前i个数,其中伤害是j,要使用的最少天数
然后发现伤害j最后只有6e5左右
首先放大招如果0,1次的话就乱搞,下面考虑两次的
一个比较暴力的方法就是
先枚举k (1---100) 然后再枚举C1
这样是6e5*100*20 有点高吧
考虑一下不去枚举k
我们设两次伤害分别为x1,x2
那么要满足x1+x2<=CC
另外,d[x1]+d[x2]+(c-x1-x2)>=D
对于第二个式子 写成 (d[x1]-x1)+(d[x2]-x2)>=D-CC
然后就维护一下最小值就好了
我并不是很理解网上为什么有人叫做单调队列。。。它的取值范围是只增不减的啊。。
最新文章
- 记录一下折腾webp 的过程
- 2013成都网络赛 J A Bit Fun(水题)
- IOS 关于NSString类型的属性为什么有时用copy,有时用strong呢?
- 2015百度之星1002 查找有序序列(RMQ+主席树模板水过)
- 《30天自制操作系统》04_day_学习笔记
- Cheatsheet: 2013 09.10 ~ 09.21
- Metadata Lock原理6
- 解决ie8不兼容jquery trim问题
- Gradle实战教程之依赖管理
- 转:基于科大讯飞语音API语音识别开发详解
- Servlet、SPringMVC、Struts等防止表单反复提交的多种处理方法
- Iveely Search Engine 0.4.0 的发布
- 自定义view实现阻尼效果的加载动画
- 微信内无法自动跳转外部浏览器打开H5分享链接的解决办法
- Mybatis学习(四)————— 高级映射,一对一,一对多,多对多映射
- 1.2 认识python(了解)
- Python 全栈开发九 日志模块
- HDOJ2089 不要62
- Tomcat 访问Manager APP报403错误
- c#面向对象基础4