2018.10.15 NOIP训练 百事世界杯之旅（期望dp）
2024-09-27 16:25:01
传送门
期望题。
其实跟dpdpdp关系并不大。
考虑f[i]f[i]f[i]表示已经凑出了iii个需要的次数。
显然有：f[i]=ni∗f[i]+nn−i∗f[i+1]+1f[i]=\frac {n} {i}*f[i]+\frac {n} {n-i}*f[i+1]+1f[i]=in∗f[i]+n−in∗f[i+1]+1
那么就有f[i]=f[i+1]+nn−if[i]=f[i+1]+\frac {n} {n-i}f[i]=f[i+1]+n−in
所以ans=f[0]=∑i=1nnians=f[0]=\sum _{i=1} ^n \frac {n} {i}ans=f[0]=∑i=1nin
然后按照题目中的格式输出就行了。
代码
最新文章
- 【总结】.Net面试题集锦 (二)
- Sql Server系列：日期和时间函数
- Django 1.10 中文文档------3.3.8 会话sessions
- JMeter学习（三十五）使用jmeter来发送json/gzip格式数据
- python之路-Day1
- HQL
- linux中的配置文件
- 生产者/消费者问题的多种Java实现方式--转
- 有关html，css,js,less的使用规范
- linux环境下安装redis扩展
- selenium2自动化测试学习笔记（五）-参数化编程，自动登陆网易QQ邮箱
- Linux CentOS7 安装wkhtmltopdf工具
- SharePoint Column Format
- python之装饰器初识
- element-ui表单form和rules踩坑
- 【XSY2669】归并排序 树状数组 简单组合数学
- LwIP协议栈规范翻译——摘要目录
- 涂抹mysql笔记-管理mysql服务
- vue中的dom基本渲染
- spring security demo