热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

优化后的标题:洛谷P3239[HNOI2015]亚瑟王算法详解与实现

题目描述:小K不幸被LL邪教洗脑,洗脑程度之深使他决定彻底脱离这个邪教。在最终离开前,他计划再进行一次亚瑟王游戏。作为最后一战,他希望这次游戏能够尽善尽美。众所周知,亚瑟王游戏的结果很大程度上取决于运气,但通过合理的策略和算法优化,可以提高获胜的概率。本文将详细解析洛谷P3239[HNOI2015]亚瑟王问题,并提供具体的算法实现方法,帮助读者更好地理解和应用相关技术。

题目描述

小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。

作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。

本题中我们将考虑游戏的一个简化版模型。 玩家有一套卡牌,共 n张。游戏时,玩家将 n 张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为 1 ~ n。本题中,顺序已经确定,即为输入的顺序。每张卡牌都有一个技能。第 i 张卡牌的技能发动概率为 pi,如果成功发动,则会对敌方造成di点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小K非洲血统的考虑,pi不会为 0,也不会为 1,即 0

1如果这张卡牌在这一局游戏中已经发动过技能,则

1.1 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌); 否则(是最后一张),结束这一轮游戏。

2否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第 i 张

2.1将其以 pi的概率发动技能。

2.2如果技能发动,则对敌方造成 di点伤害,并结束这一轮。

2.3如果这张卡牌已经是最后一张(即 i 等于n),则结束这一轮;否则,考虑下一张卡牌。

请帮助小 K 求出这一套卡牌在一局游戏中能造成的伤害的期望值。

输入输出格式


输入格式:

输入文件的第一行包含一个整数 T,代表测试数据组数。 接下来一共 T 组数据。 每组数据的第一行包含两个用空格分开的整数 n和r,分别代表卡牌的张数和游戏的轮数。 接下来 n行,每行包含一个实数和一个整数,由空格隔开,描述一张卡牌。第i 行的两个数为 pi和 di,分别代表第 i 张卡牌技能发动的概率(实数)和技能发动造成的伤害(整数)。保证 pi最多包含 4位小数,且为一个合法的概率。

输出格式:

对于每组数据,输出一行,包含一个实数,为这套卡牌在这一局游戏中造成的伤害的期望值。对于每一行输出,只有当你的输出和标准答案的相对误差不超过10^-8时——即|a-o|/a<=10-8时(其中a是标准答案,o是输出),你的输出才会被判为正确。建议输出10 位小数。

输入输出样例


输入样例#1:

1

3 2

0.5000 2

0.3000 3

0.9000 1

输出样例#1:

3.2660250000

说明

一共有 13 种可能的情况:

第一轮中,第 1张卡牌发动技能;第二轮中,第 2张卡牌发动技能;

概率为 0.15,伤害为5。

第一轮中,第 1张卡牌发动技能;第二轮中,第 3张卡牌发动技能;

概率为 0.315,伤害为3。

第一轮中,第 1张卡牌发动技能;第二轮不发动技能;

概率为 0.035,伤害为2。

第一轮中,第 2张卡牌发动技能;第二轮中,第 1张卡牌发动技能;

概率为 0.075,伤害为5。

第一轮中,第 2张卡牌发动技能;第二轮中,第 3张卡牌发动技能;

概率为 0.0675,伤害为4。

第一轮中,第 2张卡牌发动技能;第二轮不发动技能;

概率为 0.0075,伤害为3。

第一轮中,第 3张卡牌发动技能;第二轮中,第 1张卡牌发动技能;

概率为 0.1575,伤害为3。

第一轮中,第 3张卡牌发动技能;第二轮中,第 2张卡牌发动技能;

概率为 0.04725,伤害为4。

第一轮中,第 3张卡牌发动技能;第二轮不发动技能;

概率为 0.11025,伤害为1。

第一轮不发动技能;第二轮中,第 1张卡牌发动技能;

概率为 0.0175,伤害为2。

第一轮不发动技能;第二轮中,第 2张卡牌发动技能;

概率为 0.00525,伤害为3。

第一轮不发动技能;第二轮中,第 3张卡牌发动技能;

概率为 0.011025,伤害为1。

第一轮不发动技能;第二轮亦不发动技能;

概率为 0.001225,伤害为0。

造成伤害的期望值为概率与对应伤害乘积之和,为 3.266025。

对于所有测试数据, 1 <= T <= 444, 1 <= n <= 220, 0 <= r <= 132, 0

除非备注中有特殊说明,数据中 pi与di均为随机生成。

请注意可能存在的实数精度问题,并采取适当措施。

【spj】

题解

https://www.luogu.org/problemnew/solution/P3239

第一篇题解,写的蛮好

转载侵删。

如果能够求出每张卡牌在所有\(r\) 轮中被发动的概率\(g[]\) ,那么答案显然为:

\(\sum_{i=1}^ng[i]d[i]\)

第一步推出,\(g[1]=1-(1-p[1])^r\)

再考虑第二张:

情况一:如果第\(1\) 张牌没有发动过技能,那么第\(2\) 张牌发动技能的概率为\(1-(1-p[2])^r\)

情况二:如果第\(1\) 张牌发动过\(1\)次技能,那么在\(1\)张牌发动技能的那一轮,第\(2\)张牌绝对不会再发动技能了,因此第\(2\) 张牌发动技能的概率为\(1-(1-p[2])^{r-1}\)

结合这个例子,可以得到,对于任意的\(i>1\),在第1 张牌到第\(i?1\)张牌在所有\(r\) 轮内是否发动技能已经确定的情况下,第\(i\)张牌被发动技能的概率只取决于第\(1\) 张牌到第\(i?1\) 张牌中有多少张发动了技能。即如果有\(j\) 张发动了技能,那么在此情况下第\(i\) 张牌发动技能的概率为\(1-(1-p[i])^{r-j}\)

根据这个性质,就能想到一个DP模型:

\(f[i][j]\)表示前\(i\) 张牌中,恰好有\(j\) 张在所有\(r\)轮中被发动过的概率。

转移就比较好想了。分第iii 张牌发动与不发动两种情况:

1:发动。那么前\(i?1\) 张牌一定有\(j?1\)张牌被发动技能,因此对于第\(i\) 张牌,在\(r\) 轮中有\(j?1\) 轮已经不会再发动技能了。所以:

\(f[i][j]+=(1-(1-p[i])^{r-j+1})f[i-1][j-1]\)

2:不发动。那么前\(i?1\) 张牌中一定有\(j\) 张牌被发动技能,因此对于第\(i\) 张牌,在\(r\)轮中有\(j\) 轮是绝对不会再发动技能的。所以:

\(f[i][j]+=(1-p[i])^{r-j}f[i-1][j]\)

因此,完整的转移方程为:

\(f[i][j]=((1-(1-p[i])^{r-j+1})f[i-1][j-1])[j>0]\)

\(+((1-p[i])^{r-j}f[i-1][j])[i\neq j]\)

那么求\(g\) 就更容易了:

\(g[i]=\sum_{j=0}^{\min(i-1,r)}(1-(1-p[i])^{r-j})f[i-1][j]\)

代码:

#include
#include
#include
#include
#include
#include
#include
inline int max(int a, int b){return a > b ? a : b;}
inline int min(int a, int b){return a inline void swap(int &x, int &y){int tmp = x;x = y;y = tmp;}
inline void read(int &x)
{
x = 0;char ch = getchar(), c = ch;
while(ch <&#39;0&#39; || ch > &#39;9&#39;) c = ch, ch = getchar();
while(ch <= &#39;9&#39; && ch >= &#39;0&#39;) x = x * 10 + ch - &#39;0&#39;, ch = getchar();
if(c == &#39;-&#39;) x = -x;
}
const int INF = 0x3f3f3f3f;
const int MAXN = 220 + 5;
const int MAXR = 132 + 5;
int t, n, r, d[MAXN];
double p[MAXN], g[MAXN], dp[MAXN][MAXN], pow[MAXN][MAXR], ans;
/*
dp[i][j]表示前i个,在r轮中有j个发动了的概率
*/
int main()
{
freopen("data.txt", "r", stdin);
read(t);
for(;t;-- t)
{
read(n), read(r), dp[0][0] = 1, ans = 0;
for(int i = 1;i <= n;++ i) pow[i][0] = 1;
for(int i = 1;i <= n;++ i)
{
scanf("%lf", &p[i]);read(d[i]);
for(int j = 1;j <= r;++ j)
pow[i][j] = pow[i][j - 1] * (1.0 - p[i]);
}
for(int i = 1;i <= n;++ i)
for(int j = min(r, i);j >= 0;-- j)
{
if(j > 0) dp[i][j] += dp[i - 1][j - 1] * (1.0 - pow[i][r - j + 1]);
if(i != j) dp[i][j] += dp[i - 1][j] * pow[i][r - j];
}
for(int i = 1;i <= n;++ i)
for(int j = min(r - 1, i - 1);j >= 0;-- j)
g[i] += dp[i - 1][j] * (1.0 - pow[i][r - j]);
for(int i = 1;i <= n;++ i) ans += g[i] * d[i];
printf("%.10lf\n", ans);
}
return 0;
}


推荐阅读
  • POJ 1696: 空间蚂蚁算法优化与分析
    针对 POJ 1696 的空间蚂蚁算法进行了深入的优化与分析。本研究通过改进算法的时间复杂度和空间复杂度,显著提升了算法的效率。实验结果表明,优化后的算法在处理大规模数据时表现优异,能够有效减少计算时间和内存消耗。此外,我们还对算法的收敛性和稳定性进行了详细探讨,为实际应用提供了可靠的理论支持。 ... [详细]
  • JVM参数设置与命令行工具详解
    JVM参数配置与命令行工具的深入解析旨在优化系统性能,通过合理设置JVM参数,确保在高吞吐量的前提下,有效减少垃圾回收(GC)的频率,进而降低系统停顿时间,提升服务的稳定性和响应速度。此外,本文还将详细介绍常用的JVM命令行工具,帮助开发者更好地监控和调优JVM运行状态。 ... [详细]
  • 1. 给定一个包含 n 个整数的数组 a 和一个整数 x,需要判断数组中是否存在两个不同的元素,它们的和恰好等于 x。2. 反转数对问题:对于一个包含 n 个不同元素的数组 A[1...n],如果存在 i < j 且 A[i] > A[j],则称 (i, j) 为一个反转数对。本文将详细探讨这两种与归并排序相关的算法题目,并提供高效的解决方案。 ... [详细]
  • Go语言中的高效排序与搜索算法解析
    在探讨Go语言中高效的排序与搜索算法时,本文深入分析了Go语言提供的内置排序功能及其优化策略。通过实例代码,详细讲解了如何利用Go语言的标准库实现快速、高效的排序和搜索操作,为开发者提供了实用的编程指导。 ... [详细]
  • 在 Linux 系统中,`/proc` 目录实现了一种特殊的文件系统,称为 proc 文件系统。与传统的文件系统不同,proc 文件系统主要用于提供内核和进程信息的动态视图,通过文件和目录的形式呈现。这些信息包括系统状态、进程细节以及各种内核参数,为系统管理员和开发者提供了强大的诊断和调试工具。此外,proc 文件系统还支持实时读取和修改某些内核参数,增强了系统的灵活性和可配置性。 ... [详细]
  • 高效排序算法是提升数据处理速度的重要技术。通过优化排序算法,可以显著提高数据处理的效率和性能。本文介绍了几种常见的高效排序算法,如快速排序、归并排序和堆排序,并通过实例代码展示了它们的具体实现。实验结果表明,这些算法在大规模数据集上的表现尤为突出,能够有效减少数据处理时间,提升系统整体性能。 ... [详细]
  • 在 Codeforces Global Round 3 的 B 题 "Inherent Talent" 中,主人公潇洒哥需要从 A 地前往 C 地,但两地之间没有直飞航班。他可以选择在 A 地和 B 地之间的中转航班,以便尽快抵达目的地 C。该问题的核心在于如何合理安排中转,以实现最短的旅行时间。 ... [详细]
  • 如何在Java中高效构建WebService
    本文介绍了如何利用XFire框架在Java中高效构建WebService。XFire是一个轻量级、高性能的Java SOAP框架,能够简化WebService的开发流程。通过结合MyEclipse集成开发环境,开发者可以更便捷地进行项目配置和代码编写,从而提高开发效率。此外,文章还详细探讨了XFire的关键特性和最佳实践,为读者提供了实用的参考。 ... [详细]
  • Go语言实现Redis客户端与服务器的交互机制深入解析
    在前文对Godis v1.0版本的基础功能进行了详细介绍后,本文将重点探讨如何实现客户端与服务器之间的交互机制。通过具体代码实现,使客户端与服务器能够顺利通信,赋予项目实际运行的能力。本文将详细解析Go语言在实现这一过程中的关键技术和实现细节,帮助读者深入了解Redis客户端与服务器的交互原理。 ... [详细]
  • CodeForces 722C 数组破坏算法解析与优化策略 ... [详细]
  • 技术日志:深入探讨Spark Streaming与Spark SQL的融合应用
    技术日志:深入探讨Spark Streaming与Spark SQL的融合应用 ... [详细]
  • 在Spring框架中,基于Schema的异常通知与环绕通知的实现方法具有重要的实践价值。首先,对于异常通知,需要创建一个实现ThrowsAdvice接口的通知类。尽管ThrowsAdvice接口本身不包含任何方法,但开发者需自定义方法来处理异常情况。此外,环绕通知则通过实现MethodInterceptor接口来实现,允许在方法调用前后执行特定逻辑,从而增强功能或进行必要的控制。这两种通知机制的结合使用,能够有效提升应用程序的健壮性和灵活性。 ... [详细]
  • SQLmap自动化注入工具命令详解(第28-29天 实战演练)
    SQL注入工具如SQLMap等在网络安全测试中广泛应用。SQLMap是一款开源的自动化SQL注入工具,支持12种不同的数据库,具体支持的数据库类型可在其插件目录中查看。作为当前最强大的注入工具之一,SQLMap在实际应用中具有极高的效率和准确性。 ... [详细]
  • 深入解析 iOS Objective-C 中的对象内存对齐规则及其优化策略
    深入解析 iOS Objective-C 中的对象内存对齐规则及其优化策略 ... [详细]
  • 深入理解Spark框架:RDD核心概念与操作详解
    RDD是Spark框架的核心计算模型,全称为弹性分布式数据集(Resilient Distributed Dataset)。本文详细解析了RDD的基本概念、特性及其在Spark中的关键操作,包括创建、转换和行动操作等,帮助读者深入理解Spark的工作原理和优化策略。通过具体示例和代码片段,进一步阐述了如何高效利用RDD进行大数据处理。 ... [详细]
author-avatar
我是yingh_303
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有