贵阳市住房城乡建设局八大员网站,wordpress 输出 文章时间,建公司网站需要自己有系统吗,重庆有几个区几个县Description 小 K 不慎被 LL 邪教洗脑了#xff0c;洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。 他决定#xff0c;在脱坑之前#xff0c;最后再来打一盘亚瑟王。既然是最后一战#xff0c;就一定要打得漂亮。众所周知#xff0c;亚瑟王是一个看脸的游戏#xff0c;技能…Description 小 K 不慎被 LL 邪教洗脑了洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。 他决定在脱坑之前最后再来打一盘亚瑟王。既然是最后一战就一定要打得漂 亮。众所周知亚瑟王是一个看脸的游戏技能的发动都是看概率的。作为一个非 洲人同时作为一个前 OIer小 K 自然是希望最大化造成伤害的期望值。但他已 经多年没写过代码连 Spaly都敲不对了因此希望你能帮帮小 K让他感受一 下当欧洲人是怎样的体验。 本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌共 n张。游戏时玩家将 n 张卡牌排列成某种顺序排列后 将卡牌按从前往后依次编号为 1 ~ n。本题中顺序已经确定即为输入的顺序。 每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi如果成功发动则会对 敌方造成di点伤害。也只有通过发动技能卡牌才能对敌方造成伤害。基于现实因 素以及小K非洲血统的考虑pi不会为 0也不会为 1即 0 pi 1。 一局游戏一共有 r 轮。在每一轮中系统将从第一张卡牌开始按照顺序依次 考虑每张卡牌。在一轮中对于依次考虑的每一张卡牌 1如果这张卡牌在这一局游戏中已经发动过技能则 1.1 如果这张卡牌不是最后一张则跳过之考虑下一张卡牌 否则是最后一张结束这一轮游戏。 2否则这张卡牌在这一局游戏中没有发动过技能设这张卡牌为第 i 张 2.1将其以 pi的概率发动技能。 2.2如果技能发动则对敌方造成 di点伤害并结束这一轮。 2.3如果这张卡牌已经是最后一张即 i 等于n则结束这一轮否则 考虑下一张卡牌。 请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。 Input 输入文件的第一行包含一个整数 T代表测试数据组数。 接下来一共 T 组数据。 每组数据的第一行包含两个用空格分开的整数 n和r分别代表卡牌的张数和 游戏的轮数。 接下来 n行每行包含一个实数和一个整数由空格隔开描述一张卡牌。第 i 行的两个数为 pi和 di分别代表第 i 张卡牌技能发动的概率实数和技能发动 造成的伤害整数。保证 pi最多包含 4位小数且为一个合法的概率。 Output 对于每组数据输出一行包含一个实数为这套卡牌在这一局游戏中造成的 伤害的期望值。对于每一行输出只有当你的输出和标准答案的相对误差不超过 10^-8时——即|a-o|/a10-8时(其中a是标准答案o是输出)你的输出才会被判为正确。 建议输出10 位小数。 Sample Input 1 3 2 0.5000 2 0.3000 3 0.9000 1 Sample Output 3.2660250000 对于所有测试数据 1 T 444 1 n 220 0 r 132 0 pi 1 0 di 1000。 除非备注中有特殊说明数据中 pi与di均为随机生成。 请注意可能存在的实数精度问题并采取适当措施。 题解 先膜一波XYZ大神 这道题首先我们要想好状态数组含义 由于这是个抽卡游戏,每抽到一张卡其他卡的概率都会改变 所以我们要消除这种不方便,故设f[i][j]表示前i张卡在游戏中剩下j轮被选择的概率 对于第i-1张卡,考虑它对前i张的贡献:要么在剩下j轮都没被打出,要么它一定在某一轮中放了技能 所以这张卡对前i张卡的影响是 j轮都没打出:f[i][j]f[i-1][j]*pow(1-p[i-1],j) 某一轮打出了:f[i][j-1]f[i-1][j]*(1-pow(1-p[i-1],j)); 所以f[i][j]的递推公式是:f[i][j]f[i-1][j]*pow(1-p[i-1],j)f[i-1][j1]*(1-pow(1-p[i-1],j1)); 然后把所有f[i][j]乘上在j轮中某一轮打出的概率(1-pow(1-p[i],j)),再乘伤害d[i]然后累加,得到的就是最后答案 代码见下 #includecstdio
#includecstring
#includecmath
using namespace std;
const int N250;
const int R150;
int t,n,r,d[N];
double p[N],k[N],f[N][R];
inline void intn()
{for(int i0;iN;i)p[i]k[i]0;memset(d,0,sizeof(d));
}
int main()
{scanf(%d,t);while(t--){intn();scanf(%d%d,n,r);for(int i1;in;i)scanf(%lf%d,p[i],d[i]);for(int i0;iN;i)for(int j0;jR;j)f[i][j]0;double ans0;f[0][r]1;for(int i1;in;i)for(int j1;jr;j){f[i][j]f[i-1][j]*pow(1-p[i-1],j)f[i-1][j1]*(1-pow(1-p[i-1],j1));ansf[i][j]*(1-pow(1-p[i],j))*d[i];}printf(%.10lf\n,ans);}
} 转载于:https://www.cnblogs.com/LadyLex/p/7006906.html
