RainAir
My OI Blog
RainAir
「NOIP2016」换教室

这道题甚至不如 T2 难…放在 T3 真的合适吗…

题目链接

题目描述

一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i $ 的概率选择点 $ c_i $ ,每次选择相互独立。至多能选 $ M $ 次 $ d $ 类节点现在求出所有选择的路线方案中的最小期望值。

解题报告

~~看到期望了直接弃疗~~

这一题考的是期望的基本知识,所以大可不用弃疗。

~~感觉就是出题人为了强行增加难度套了个期望?~~

对于期望计算就是事件价值/代价 $*$ 概率,对其求和。

这样我们首先发现点非常的少,Floyd 处理最短路。

然后我们考虑动态规划。设 $ f[i][j][1/0] $ 表示考虑到第 $i$ 次选择,已经选择了 $j$ 次 $d$ 类节点,这一次是否选 $d$ 类节点的最小期望值。

显然转移方程如下:

设 $ dis[i][j] $ 表示 i 到 j 的最短路,$ c[i],d[i],p[i] $ 如题目所述。

dp转移代码如下(公式太长了写不开)

c++
f[i][j][0] = std::min(f[i-1][j][0]+map[c[i-1]][c[i]],f[i-1][j][1] + p[i-1] * map[d[i-1]][c[i]] + map[c[i-1]][c[i]] * (1.0-p[i-1]));
f[i][j][1] = std::min(f[i-1][j-1][0] + map[c[i-1]][d[i]]*p[i] + map[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1] + map[c[i-1]][c[i]] * (1-p[i-1])*(1-p[i]) + map[c[i-1]][d[i]] * (1-p[i-1])*p[i] + map[d[i-1]][c[i]] * p[i-1]*(1-p[i]) + map[d[i-1]][d[i]] * p[i-1] * p[i]);

这个方程的细节很多,还请读者自己体会。

其实就是加上所有的期望。

样例代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/92
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「NOIP2016」换教室
这道题甚至不如 T2 难...放在 T3 真的合适吗... 题目链接 题目描述 一张无向带权图,需要选择 $ N $ 次。每次在两个点 $ c_i,d_i $ 中,有 $ p_i $ 的概率选择点 $ d_i $,有 $ 1-p_i …
扫描二维码继续阅读
2018-08-17
标签
近期评论