Codeforces – 167B – Wizards and Huge Prize

题目地址:CF167B – Wizards and Huge Prize – 洛谷

题意

最开始,你有 $M$ 的容积。有 $n$ 轮比赛,对于第 $i$ 场比赛,你获胜的概率为 $p_i$.

比赛的奖励分为两种:一种是增加 $a_i$ 的容积,一种是给你 $1$ 个奖品。

一种赢比赛的合法方案,需要满足:$n$ 轮比赛结束时,总容积 $\geq $ 获得的奖品数量

求获胜场次 $\geq l$,且方案合法的概率

$1\leq M, n, a_i\leq 200$,$0\leq p_i\leq 1$.

题解

概率 DP。

显然,获得一个奖品等价于容积 $-1$,方案合法 $\Leftrightarrow$ $n$ 轮结束后的容积非负

设 $\operatorname{dp}_{i, j, k}$ 表示:前 $i$ 轮比赛后,在其中的 $j$ 场中获胜,当前可用容积为 $k$ 发生的概率。

为了方便表示,允许下标为负,则:

$$
\operatorname{Ans} = \sum_{i=l}^{n}\sum_{j=0}^{+\infty}{\operatorname{dp}_{n,i,j}}
$$

第三维数组的大小?

注意到,每次操作最多减 $1$,如果容积 $>=n$ ,就不可能不合法了,都和 $n$ 的状态等价。

所以有意义的可用容积在 $[-n, n]$ 范围内,空间开 $2\times n$ 即可,答案的表达式也可以改写为:

$$
\operatorname{Ans} = \sum_{i=l}^{n}\sum_{j=0}^{n}{\operatorname{dp}_{n,i,j}}
$$

考虑如何转移?

刷表,状态 $(i, j, k)$ 只会贡献到 $(i+1, j, k)$ 或 $(i+1, j+1, \min\{n, k+a_{i+1}\})$.

两种转移分别对应 赢/不赢 第 $i+1$ 轮,具体地:

$$
\begin{array}{rcl}
(1-p_{i+1})\times \operatorname{dp}_{i,j,k}&\rightarrow &\operatorname{dp}_{i+1,j,k}\\
p_{i+1}\times \operatorname{dp}_{i,j,k}&\rightarrow &\operatorname{dp}_{i+1, j+1, \min\{n,k+a_{i+1}\}}
\end{array}
$$

时空复杂度均为 $\mathcal{O}(n^3)$.

代码

实现时,注意将第三维坐标整体 $+n$.

const int N = 200;

dp[0][0][N + K] = 1.0;
for(int i = 0; i < n; i++) {
    for(int j = 0; j <= i; j++) {
        for(int k = 0; k <= (N << 1); k++) {
            dp[i + 1][j][k] += (1.0 - p[i + 1]) * dp[i][j][k];
            int nxt = min((N << 1), k + a[i + 1]);
            if(nxt >= 0) dp[i + 1][j + 1][nxt] += p[i + 1] * dp[i][j][k];
        }
    }
}

for(int i = l; i <= n; i++) {
    for(int j = N; j <= (N << 1); j++) {
        ans += dp[n][i][j];
    }
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();