【ZOJ】3640 Help Me Escape
2024-10-08 01:05:27
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4808
题意:一个吸血鬼初始攻击力为f。n条路,他每次等概率选择一条路。如果攻击力大于这条路的c[i],则花费t[i]天逃出($t[i]=\frac{1+\sqrt{5}}{2} \times c[i]^2$),否则花费1天的时间继续选择路。问逃出去的期望天数(1<=c[i], f<=10000)
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N=20005;
double f[N];
int n, c[N], t[N];
double E(int x) {
if(f[x]>0) return f[x];
double &now=f[x];
for(int i=0; i<n; ++i) {
if(x>c[i]) now+=t[i];
else now+=E(x+c[i])+1;
}
now/=n;
return now;
}
int main() {
int now;
while(~scanf("%d%d", &n, &now)) {
for(int i=0; i<n; ++i) scanf("%d", &c[i]), t[i]=(1.0+sqrt(5))/2*c[i]*c[i];
printf("%.3f\n", E(now));
memset(f, 0, sizeof f);
}
return 0;
}
简单题无脑dp= =
设$f[i]$表示攻击力为$i$时逃出去所需要的期望天数..随便搞一下就行了..
最新文章
- 关于SharePoint 2013的工作流(二)
- 使用CSS3动画模拟实现小球自由落体效果
- c# 反射列子
- 点击li,点击的li添加class,其余去掉class
- Codevs 1009 产生数
- GB2312 简体中文编码表
- HTML5的渐变色 渐变的两种类型 createLinearGradient 和createRadialGradient
- PV、UV、IP的区别
- java多态---ABC案列
- 2013年五大主流浏览器 HTML5 和 CSS3 兼容性大比拼
- JAVA的DES加密解密在windows上测试一切正常,在linux上异常
- JavaScript变量声明var,let.const
- Tomcat启动特慢之SecureRandom问题解决
- [原] MyBatis 整理
- python基础类型—列表
- 深入剖析Java中的装箱和拆箱(缓存池技术)
- poj3278 Catch That Cow(简单的一维bfs)
- Java基础三(Scanner键盘输入、Random随机数、流程控制语句)
- node下使用jquery
- mysql官方下载
热门文章
- PHP获取远程图片并调整图像大小(转)
- Delphi运算符总结
- IE文档版本和文档流模式
- poj 1195:Mobile phones(二维树状数组,矩阵求和)
- Linux进程状态 ( Linux Process State Codes)
- Implementing Navigation with UINavigationController
- hdu 4389 数位dp
- [Eclipse] Eclipse字体问题解决
- ViewPager onPageChangeListener总结(转)
- 编译器 expected unqualified-id before numeric constant 错误