BZOJ 4008 - [HNOI2015]亚瑟王

Published on 2016-11-27

题目地址

描述

小 K 不慎被 LL 邪教洗脑了,洗脑程度深到他甚至想要从亚瑟王邪教中脱坑。他决定,在脱坑之前,最后再来打一盘亚瑟王。既然是最后一战,就一定要打得漂亮。众所周知,亚瑟王是一个看脸的游戏,技能的发动都是看概率的。作为一个非洲人,同时作为一个前 OIer,小 K 自然是希望最大化造成伤害的期望值。但他已经多年没写过代码,连 Spaly 都敲不对了,因此,希望你能帮帮小 K,让他感受一下当欧洲人是怎样的体验。
本题中我们将考虑游戏的一个简化版模型。玩家有一套卡牌,共 n(n220)n(n\le 220) 张。游戏时,玩家将 nn 张卡牌排列成某种顺序,排列后将卡牌按从前往后依次编号为 。本题中,顺序已经确定,即为输入的顺序。每张卡牌都有一个技能。第 ii 张卡牌的技能发动概率为 pip_i,如果成功发动,则会对敌方造成 did_i 点伤害。也只有通过发动技能,卡牌才能对敌方造成伤害。基于现实因素以及小 K 非洲血统的考虑,pip_i 不会为 0,也不会为 1,即 0<pi<10 < p_i < 1
一局游戏一共有 r(r132)r(r\le 132) 轮。在每一轮中,系统将从第一张卡牌开始,按照顺序依次考虑每张卡牌。在一轮中,对于依次考虑的每一张卡牌:

  1. 如果这张卡牌在这一局游戏中已经发动过技能,则:
    1. 如果这张卡牌不是最后一张,则跳过之(考虑下一张卡牌);
    2. 否则(是最后一张),结束这一轮游戏。
  2. 否则(这张卡牌在这一局游戏中没有发动过技能),设这张卡牌为第 i 张:
    1. 将其以 pip_i 的概率发动技能。
    2. 如果技能发动,则对敌方造成 did_i 点伤害,并结束这一轮。
    3. 如果这张卡牌已经是最后一张(即 ii 等于 nn),则结束这一轮;否则,考虑下一张卡牌。

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

分析

根据期望的线性性质,造成伤害的期望值等于这局游戏中每张卡牌发动的概率 PiP_i 乘上这张卡牌造成的伤害 did_i,现在问转化为了怎么求 PiP_i
我们设 dpi,jdp_{i, j} 为已经考虑了前 ii 张牌,还剩 jj 轮发生的概率。已经考虑了前 ii 张牌的意思是,在剩下的 jj 轮中,保证前 ii 张不会被选,即我们的考虑的卡牌起点变成了 i+1i + 1。边界情况是 dp0,r=1dp_{0, r} = 1

我们考虑转移,假设已经求出了 dpi,jdp_{i, j},考虑 i+1i + 1 是否在接下来的 jj 轮中被选中:
如果没有被选中,概率是 (1pi+1)j{(1 - p_{i + 1})}^j,刷表转移到 dpi+1,jdp_{i + 1, j}

dpi+1,jdpi,j(1pi+1)jdp_{i + 1, j}\leftarrow dp_{i, j}\cdot {(1 - p_{i + 1})}^j

如果被选中,概率是 1(1pi+1)j1 - {(1 - p_{i + 1})}^j,由于选中了,所以消耗掉了一轮,刷表转移到 dpi+1,j1dp_{i + 1, j - 1}

dpi+1,j1dpi,j(1(1pi+1)j)dp_{i + 1, j - 1}\leftarrow dp_{i, j}\cdot (1 - {(1 - p_{i + 1})}^j)

那么这个 DP 跟 PiP_i 有什么关系呢?实际上, 这个状态,是所有局面发展过程中必然经历的一个状态。因为根据我们的转移,必然有恒等式:

0jrdpi,j=1\sum_{0\le j\le r}dp_{i, j} = 1

也就是说,无论是如何出的牌,都必然会经历一个 dpi,x(0xr)dp_{i, x}(0\le x\le r) 的局面。我们在每一个局面 dpi,jdp_{i, j} 中,知道了 i+1i + 1 被选中的概率,那么,根据全概率公式,也就知道了整局游戏中中 i+1i + 1 被选中的概率(i+1i + 1 之后的卡牌不会影响 i+1i + 1 的概率):

Pi+1=0jrdpi,j(1(1pi+1)j)P_{i + 1} = \sum_{0\le j\le r}dp_{i, j}\cdot (1 - {(1 - p_{i + 1})}^j)

所以我们就能求出 PiP_i 来,答案也就不难算出。复杂度:O(Tnr)O(Tnr)

这个 DP,并不直观的包含了所有可能的局面(我们花了一番功夫证明了这一点),所以它可以使用期望的线性性质单独计算贡献。这就是 概率与期望 DP 总结 中的方法二。

代码

//  Created by Sengxian on 2016/11/27.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 4008 概率 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 220 + 3, MAX_M = 132 + 3;
const double eps = 1e-8;
int n, m, d[MAX_N];
double p[MAX_N], P[MAX_N], dp[MAX_N][MAX_M];

void solve() {
    memset(dp, 0, sizeof dp);
    memset(P, 0, sizeof P);
    dp[0][m] = 1.0;
    for (int i = 0; i < n; ++i) {
        double t = 1.0;
        for (int j = 0; j <= m; ++j) {
            dp[i + 1][j] += dp[i][j] * t;
            if (j) dp[i + 1][j - 1] += dp[i][j] * (1 - t);
            P[i] += dp[i][j] * (1 - t), t *= (1 - p[i]);
        }
    }
    for (int j = 0; j < m; ++j) {
        double t = 0;
        for (int i = 0; i <= n; ++i) t += dp[j][i];
        cout << t << endl;
    }
    double ans = 0;
    for (int i = 0; i < n; ++i) ans += P[i] * d[i];
    printf("%.10f\n", ans);
}

int main() {
    int caseNum = readInt();
    while (caseNum--) {
        n = readInt(), m = readInt();
        for (int i = 0; i < n; ++i) scanf("%lf%d", p + i, d + i);
        solve();
    }
    return 0;
}