焦点滚动:rr轮游戏中前ii个物品有多少个被选到？

题目传送门

题目大意：有 n n n 个物品，进行 r r r 轮游戏，每轮中从左到右依次选择物品，每个物品有 p [ i ] p[i] p[i] 的几率被选到，被选过的不会再选，每轮游戏只选一个物品，第 i i i 个物品价值为 d [ i ] d[i] d[i]，问期望价值。

(资料图)

题解

第 i i i 个物品在 r r r 轮游戏中被选到的几率取决去前 i − 1 i-1 i−1 个物品有多少个被选到了，假如有 k k k 个，那么第 i i i 个物品被选到的概率就是 1 − ( 1 − p [ i ] ) r − k 1-(1-p[i])^{r-k} 1−(1−p[i])r−k， ( 1 − p [ i ] ) r − k (1-p[i])^{r-k} (1−p[i])r−k 的意思是剩下 r − k r-k r−k 轮中每一轮都选不到 i i i 的概率，用 1 1 1 减掉就是有任意一轮选到的概率了。

那么可以得到递推方程：设 f [ i ] [ j ] f[i][j] f[i][j] 表示在 r r r 轮游戏中前 i i i 个物品有 j j j 个被选到的概率，那么有 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] × ( 1 − ( 1 − p [ i ] ) r − j + 1 ) [ j > 0 ] + f [ i − 1 ] [ j ] × ( 1 − p [ i ] ) r − j \begin{aligned} f[i][j]=&f[i-1][j-1]\times (1-(1-p[i])^{r-j+1})[j>0]+\\ &f[i-1][j]\times(1-p[i])^{r-j} \end{aligned} f[i][j]=f[i−1][j−1]×(1−(1−p[i])r−j+1)[j>0]+f[i−1][j]×(1−p[i])r−j

柿子中上面的表示选到第 i i i 个的概率，下面表示选不到的概率。

求出 f f f 之后，我们就可以得到每个物品被选到的概率，用这个概率乘上每个物品的价值再求个和就是答案了。

第 i i i 个物品被选到的概率： ∑ j = 0 min ⁡ ( i , r ) − 1 f [ i − 1 ] [ j ] × ( 1 − ( 1 − p [ i ] ) r − j ) \sum_{j=0}^{\min(i,r)-1}f[i-1][j]\times(1-(1-p[i])^{r-j}) j=0∑min(i,r)−1f[i−1][j]×(1−(1−p[i])r−j)

如果你在洛谷拿到了 40 40 40 分的好成绩，那么就要注意数组初始化和答案是否换行的问题了。

代码如下：

#include#includeusing namespace std;#define maxn 230int T,n,r;double p[maxn],d[maxn],f[maxn][maxn],ans=0;double ksm(double x,int y){double re=1;while(y){if(y&1)re*=x;x*=x;y>>=1;}return re;}int main(){scanf("%d",&T);while(T--){scanf("%d %d",&n,&r);for(int i=1;i<=n;i++)scanf("%lf %lf",&p[i],&d[i]);f[0][0]=1;ans=0;for(int i=1;i<=n;i++)for(int j=0;j<=min(i,r);j++){f[i][j]=ksm(1-p[i],r-j)*f[i-1][j];if(j)f[i][j]+=(1-ksm(1-p[i],r-j+1))*f[i-1][j-1];}for(int i=1;i<=n;i++){double tot=0;for(int j=0;j<=min(i,r)-1;j++)tot+=(1-ksm(1-p[i],r-j))*f[i-1][j];ans+=tot*d[i];}printf("%.10lf\n",ans);}}