BZOJ4008 [HNOI2015]亚瑟王

题意

小K不慎被LL邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。

他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。作为一个非洲人,同时作为一个前OIer,小K自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连Spaly都敲不对了,因此,希望你能帮帮小K,让他感受一下当欧洲人是怎样的体验。
本题中我们将考虑游戏的一个简化版模型。
玩家有一套卡牌,共$n$张。游戏时,玩家将$n$张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为$1$~$n$。本题中,顺序已经确定,即为输入的顺序。
每张卡牌都有一个技能。第$i$张卡牌的技能发动概率为$p_i$,如果成功发动,则会对敌方造成$d_i$点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小K非洲血统的考虑,$p_i$不会为$0$,也不会为$1$,即$0<p_i<1$。
一局游戏一共有$r$轮。在每一轮中,系统将从第一张卡牌开始,按照顺序依次
考虑每张卡牌。在一轮中,对于依次考虑的每一张卡牌:
1 如果这张卡牌在这一局游戏中已经发动过技能,则
1.1 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌);否则(是最后一张),结束这一轮游戏。
2 否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第$i$张
2.1 将其以$p_i$的概率发动技能。
2.2 如果技能发动,则对敌方造成$d_i$点伤害,并结束这一轮。
2.3 如果这张卡牌已经是最后一张(即$i$等于$n$),则结束这一轮;否则,考虑下一张卡牌。
请帮助小K求出这一套卡牌在一局游戏中能造成的伤害的期望值。
$1 \leqslant T \leqslant 444,1 \leqslant n \leqslant 220,0 \leqslant r \leqslant 132,0 < p_i < 1,0 \leqslant d_i \leqslant 1000$。

题解

话说这次HNOI我还考过……只是那时是真的太渣了,竟然爆0了= =。
不难想到概率DP。但注意到一个很烦人的问题,就是每张卡牌在发动完技能之后,就要退出这套卡牌,而普通的DP总是跳不出记录哪些卡牌已经使用过这一状态,而这个问题搞不定,就是个暴力了……我们不考虑普通的按照游戏的顺序DP,而是选择按照每张卡牌的顺序。即不考虑横向的DP,而是选择纵向的DP。记$dp[i][j]$表示在前$i$张卡牌,还有$j$张卡牌没有发动技能的概率。那么就有这样的转移方程:
$$dp[i][j]=dp[i-1][j] \times (1-p_i)^j+dp[i-1][j+1]*(1-(1-p_i)^{j+1})$$
稍微解释一下这个奇怪的式子。第一项表示不选择这一张卡牌,由于还有$j$张卡牌没有发动过,即还会考虑这张卡牌$j$次,故要乘上$(1-p_i)^j$的概率;第二项表示选择这张卡牌,那么用全部概率减去接下来的$j+1$次考虑这张卡牌的时候,都不选择它的概率,就是要乘的概率了,即$1-(1-p_i)^{j+1}$。
然后再顺便把期望求一下就好了。期望的式子长这样:
$$E[i][j]=E[i-1][j] \times (1-p_i)^j+(E[i-1][j+1]+d_i \times dp[i-1][j+1]) \times (1-(1-p_i)^{j-1})$$
意义与上一个式子很类似。
时间复杂度$O(nrT)$。
时间稍微有点卡,需要预处理幂。
话说这题DP的式子是真的难调,到处乘错概率……我改了半个晚上才调过去……真的菜。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=220+10;
const int maxm=132+10;
long double p[maxn],dp[maxn][maxm],P[maxn][maxm],Pow[maxn][maxm];
int d[maxn];
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
int main(){
int i,j,k,m,n,T;
#ifndef ONLINE_JUDGE
freopen("BZOJ4008.in","r",stdin);
freopen("BZOJ4008.out","w",stdout);
#endif
T=read();
while(T--){
n=read();m=read();
memset(dp,0,sizeof(dp));
memset(P,0,sizeof(P));
for(i=1;i<=n;i++)scanf("%Lf",&p[i]),d[i]=read();
for(i=1;i<=n;i++){
Pow[i][0]=1;
for(j=1;j<=m+1;j++)
Pow[i][j]=Pow[i][j-1]*(1-p[i]);
}
P[0][m]=1;
for(i=1;i<=n;i++)
for(j=m;j>=0;j--){
P[i][j]=P[i-1][j]*Pow[i][j]+P[i-1][j+1]*(1-Pow[i][j+1]);
if(j==m)continue;
dp[i][j]=dp[i-1][j]*Pow[i][j]+(dp[i-1][j+1]+d[i]*P[i-1][j+1])*(1-Pow[i][j+1]);
}
long double ans=0;
for(i=0;i<=m;i++)ans+=dp[n][i];
printf("%.15Lf\n",ans);
}
return 0;
}