Sengxian's Blog

题目地址

描述

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

1. 如果这张卡牌在这一局游戏中已经发动过技能，则：
   1. 如果这张卡牌不是最后一张，则跳过之（考虑下一张卡牌）；
   2. 否则（是最后一张），结束这一轮游戏。
2. 否则（这张卡牌在这一局游戏中没有发动过技能），设这张卡牌为第 i 张：
   1. 将其以 $p_i$ 的概率发动技能。
   2. 如果技能发动，则对敌方造成 $d_i$ 点伤害，并结束这一轮。
   3. 如果这张卡牌已经是最后一张（即 $i$ 等于 $n$），则结束这一轮；否则，考虑下一张卡牌。

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

分析

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

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

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

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

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

所以我们就能求出 $P_i$ 来，答案也就不难算出。复杂度：$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;
}