概率DP——BZOJ4008 [HNOI2015]亚瑟王
[HNOI2015]亚瑟王
Description
小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。 本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌,共 n张。游戏时,玩家将 n 张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为 1 ~ n。本题中,顺序已经确定,即为输入的顺序。每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi,如果成功发动,则会对敌方造成di点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小K非洲血统的考虑,pi不会为 0,也不会为 1,即 0 < pi < 1。
Input
输入文件的第一行包含一个整数 T,代表测试数据组数。
Output
对于每组数据,输出一行,包含一个实数,为这套卡牌在这一局游戏中造成的伤害的期望值。对于每一行输出,只有当你的输出和标准答案的相对误差不超过10^-8时——即|a-o|/a<=10-8时(其中a是标准答案,o是输出),你的输出才会被判为正确。
Sample Input
3 2
0.5000 2
0.3000 3
0.9000 1
Sample Output
HINT
一共有 13 种可能的情况:
虽然概率DP是很明显了,但是状态转移方程真鸡儿难想。
思考的角度完全错了,做题的时候一直在想如何用f[i][j]表示第i轮前j张牌的期望伤害之类的,没想到正解转移的根本不是期望。。。
实际上伤害的期望值$E=k[i]\times d[i]$,其中$k[i]$为第i张牌发动技能的概率。
于是问题就转化为了求$k[i]$
设f[i][j]为转移到第i张牌的时候,还剩j轮的概率。
显然,转移到第i张牌的时候,还剩j轮的概率为 "在i-1张牌时剩j轮并未发动技能的概率" 加上 "在i-1张牌时剩j+1轮并发动技能的概率"。即$$f[i][j]=f[i-1][j]\times(1-p[i-1])^j+f[i-1][j+1]\times(1-(1-p[i-1])^j+1)$$
那么$$E_{ans}=\sum_{i=1}^n{\sum_{j=1}^r (1-(1-p[i])^j)\times f[i][j]\times d[i]}$$
代码不长。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define foru(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
const int N=;
int n,T,r,d[N];
double p[N],ans,f[N][N];
int main(){
scanf("%d",&T);
while(T--){
memset(f,,sizeof(f));
scanf("%d%d",&n,&r);
f[][r]=;
foru(i,,n)scanf("%lf%d",&p[i],&d[i]);
double ans=;
foru(i,,n)
foru(j,,r){
f[i][j]=(double)f[i-][j]*pow(-p[i-],j)+f[i-][j+]*(-pow(-p[i-],j+));
ans+=(double)f[i][j]*(-pow(-p[i],j))*d[i];
}
printf("%.10lf\n",ans);
}
return ;
}
最新文章
- HTML 字符实体 &;lt; &;gt: &;amp;等
- Spring MVC 使用HiddenHttpMethodFilter配置Rest风格的URL
- 前端mvc框架backbone.js入门[转]
- MY SQL 知识
- .NET中string[]数组和List<;string>;泛型的相互转换以及Array类的Sort()方法(转)
- [ZZ] [siggraph10]color enhancement and rendering in film and game productio
- css实现“固定表头带滚动条”的table
- ligerUI路径问题
- CSS排序工具csscomb
- Spring DM所提供的Bundle监听接口OsgiBundleApplicationContextListener
- C语言之循环结构
- python调试
- javascript 原型机制
- 学习Acegi应用到实际项目中(6)
- 【golang-GUI开发】struct tags系统(二)qt的自定义组件和构造函数
- JavaScript(JS)之Javascript对象DOM(三)
- ZOJ - 3471
- php中通过Hashids将整数转化为唯一字符串
- 洛谷P4742 [Wind Festival]Running In The Sky [Tarjan缩点,DAGDP]
- (二)github的价值意义篇
热门文章
- 解决configure: error: C++ compiler cannot create executables问题
- EOJ Monthly 2020.1 E. 数的变幻
- 2.3 使用Android Studio 简单设计UI界面
- LeetCode——221. 最大正方形
- SQL基础教程(第2版)第6章 函数、谓词、CASE表达式:练习题
- Windows环境下spyder调用Arcpy
- Linux-线程同步之互斥锁
- 客户主题分析(tableau)—客户分群
- delphi控制word 标题 字符和位置
- Web应用和web.xml文件