概率dp – Tgotp-Blog

T16110 小象涂色

题目描述

小象喜欢为箱子涂色。小象现在有 c 种颜色,编号为 0~c-1;还有 n 个箱子,编号

为 1~n,最开始每个箱子的颜色为 1。小象涂色时喜欢遵循灵感:它将箱子按编号排成

一排,每次涂色时,它随机选择[L,R]这个区间里的一些箱子(不选看做选 0 个),为

之涂上随机一[......]

Read more

P2111 考场奇遇

概率dp

这一次对的某种情况为上一次少一的概率*成功的概率 + 一样*不成功的概率

c++代码如下:

 

1076: [SCOI2008]奖励关

概率dp & 状压dp

从后往前扫。

每一个掉落的概率都是1/n即如果能拿到期望值维f[i][j] = (f[i][j|(1<<z-1)] + a[i])/n

不行得话期望值只用从上一次转移过来,ok。

可以随便套一个滚动数组优化。

c++代码如下:[......]

Read more

NOIP2016T3

概率dp,数学期望,很简单的一道题。