2018.10.14 NOIP训练 猜数游戏（决策单调性优化dp）
2024-09-29 20:14:35
传送门
一道神奇的dp题。
这题的决策单调性优化跟普通的不同。
首先发现这道题只跟r−lr-lr−l有关。
然后定义状态f[i][j]f[i][j]f[i][j]表示猜范围为[L,L+i−1][L,L+i-1][L,L+i−1]的数有jjj次报警机会所需的最小代价。
那么有：
f[i][j]=minf[i][j]=minf[i][j]=min{max(f[k][j],f[i−k][j−1]+1)max(f[k][j],f[i-k][j-1]+1)max(f[k][j],f[i−k][j−1]+1)}，然后打表可以发现对于同一个jjj，kkk随着iii单增
然后就做完了。
代码
最新文章
- .NET中使用NLog记录日志
- CentOS7 修改系统时间
- C#中的volatile用法
- 文字处理TX Text Control X10独家揭秘（二）：图像占位符合并
- Linux Mint下编译Bochs
- C#委托和事件讲解
- MySQL优化---DBA对MySQL优化的一些总结
- 基于ASP.NET MVC和Bootstrap搭建响应式个人博客站（一）
- IOS开发--数据持久化篇之文件存储(一)
- Codeforces Gym 100342E Problem E. Minima 暴力
- Lua开发环境搭建（Mac)
- 项目管理Point
- AS3 Graphics 多次绘制
- poj2823_单调队列简单入门
- 求模和求余(附加C语言实现)
- 201521123048 《Java程序设计》第1周学习总结
- ansbile Tags && Block
- 查看电脑保存的wifi密码
- linux新手向-文件的权限及修改
- Python2.7-SciPy