本文共 1336 字，大约阅读时间需要 4 分钟。

题目链接：

题意

给你一个容量为n的卡牌收集册，以及无限个卡牌包，卡牌包有[a,b]个卡牌，取出的卡牌数是等概率分布的，言外之意你有$\frac{1}{b-a+1}$的概率取出a、a+1、…、b张卡牌。问你把卡牌收集册集满时的概率期望是多少。

题解

设dp[i]：你已经有i张卡牌，你要集满n张还需多少卡牌。

不难看出我们只需记录出$dp[i+a]～dp[i+b]$的和就能完成递推式。

但题目给出a可能为0

$dp[i]=\frac{(dp[i]+1)+(dp[i+1]+1)+....(dp[i+b]+1)}{b-a+1}$（取l=b-a+1）

⇒ $\frac{l-1}{l}dp[i]=\frac{dp[i+1]+dp[i+2]+...+dp[i+b]}{l}+1$

不难看出我们只需记录出$dp[i+1]～dp[i+b]$的和就能完成递推式。所以a为0的状态转移和a不为0的略有不同，需要特判。

代码

double dp[maxn];int main(){
   	int n,a,b,len;	cin >> n >> a >> b;	len=b-a+1;	dp[n]=0.0;	double sum=0.0;	for(int i=n-1;i>=0;i--)	{
   		if(!a)		{
   			dp[i]=(sum+len*1.0)/(len-1.0);			sum-=dp[i+b];			sum+=dp[i];		}		else		{
   			dp[i]=sum*1.0/len+1;			sum-=dp[i+b];			sum+=dp[i+a-1];		}	}	printf("%.8lf",dp[0]);}

转载地址：http://khmh.baihongyu.com/