题目大意:有一个吸血鬼,初始攻击力为f,每天随机走到n个洞里面,每个洞有一个c[i],如果他的攻击力f>c[i]

则可以花费t[i] 的时间逃走,否则则花费一天时间使自己的攻击力增加c[i],求逃走天数的期望

分析:

这道题求期望,,考虑采用概率dp求解

想到的最简单方法就是dp[i][j]表示 第i天,攻击力为j的概率,然后对每一个c进行转移,最后统计答案

但是发现i,j的范围都是10000,n是100 这么做显然是行不通的

于是又可耻的搜了一下题解,发现有一个博主写的期望dp这个概念很不错

令 dp[a]表示 攻击力为 a 后 还需要多少天逃出的期望,那么dp[f]即为答案

注意关键是这个 “还”

状态转移:

如果 a>c[i]  那么显然还需要 t[i]时间逃出

如果 a<=c[i] 那么先要花费一天把攻击力增加a+c[i],然后还要花费的时间就是 dp[a+c[i]]

这样转移方程就很好写了

由于需要从后往前转移,采用记忆化搜索写

开始数组开10010 老是segment fault 后来开到10W过了。。

代码:

#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
#include<math.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int n,f;
double p;
double dp[];
int c[];
bool vi[];
double dfs(int a)
{
if(vi[a])
return dp[a];
vi[a]=;
for(int i=;i<n;i++)
{
if(a>c[i])
dp[a]+=(double)floor(p*c[i]*c[i])/(double)n;
else
dp[a]+=(1.0+dfs(a+c[i]))/(double)n;
}
return dp[a];
}
int main()
{
while(scanf("%d%d",&n,&f)!=EOF)
{
for(int i=;i<n;i++)
{
scanf("%d",c+i);
}
memset(dp,,sizeof(dp));
memset(vi,,sizeof(vi));
p=(1.0+sqrt(5.0))/2.0;
printf("%.3f\n",dfs(f));
}
return ;
}

最新文章

  1. 韩国&quot;被申遗&quot; (转自果壳)
  2. response.sendRedirect()与request.getRequestDispatcher().forward()区别
  3. WPF 模板
  4. 微软modern.IE网站,多版本IE免费测试工具集
  5. Lotus 迁移到Exchange POC 之 新建2007 服务器!
  6. FLV封装格式及分析器工具
  7. about云资源汇总V1,3
  8. German Collegiate Programming Contest 2013:E
  9. Sybase Power Designer 16.5破解版下载
  10. ExcelParser ,Excel解析的工具类(正对解析xlsx)
  11. Web 开发后端缓存思路
  12. ZooKeeper数据结构
  13. SQLServer2008数据库安装图解
  14. 注解@EnableDiscoveryClient,@EnableEurekaClient的区别
  15. VMware虚拟机扩展Ubuntu系统磁盘空间
  16. IntelliJ IDEA快捷键与使用小技巧
  17. Ring3创建事件Ring0设置事件
  18. sqlserver 自动创建作业执行备份数据库
  19. Jmeter(二十二)_脚本上传Gitlab
  20. centos/rhel最小化安装图形化

热门文章

  1. 浅谈ListView滑动隐藏显示ToolBar
  2. 如何解决前端传来的时间格式与mysql表中时间格式不匹配的查询问题
  3. iOS图片加载到内存中占用内存情况
  4. linux环境内存分配原理 mallocinfo
  5. jQuery Mobile笔记
  6. java 13-6 Char的包装类Character
  7. [转]World Wind Java开发之四——搭建本地WMS服务器
  8. IOS代理
  9. Windows8.1 preview硬盘安装(图解)
  10. java 集合框架(二)Iterable接口
  11. ABP领域层知识回顾之---仓储
  12. LoadRunner(一)——性能测试基础及性能指标概述
  13. Lintcode: Nuts &amp; Bolts Problem
  14. 使用monitor.bat用DDMS查看其它项目的布局
  15. C++实现程序单实例运行的两种方式
  16. JDBC的简单笔记
  17. jq 全选与联动的小例子
  18. 学习笔记之Lazy evaluation
  19. 八大排序算法的Java代码实现
  20. stm32的swd接口的烧写协议是否公开的呢?