CF-gym-102861-A（概率DP）

题意

你想要买N张卡片，现在有一种卡包，里面有可能有最少A张，最多B张卡片。
问期望卖多少卡包，可以得到至少N张卡片。
1 <= N <= 1e6
0 <= A <= B <= 1e6
B > 0

分析

把卡包出卡的期望看作是（Ａ+B）/ 2是不正确的。

换个角度，假设抽出x张卡所需要的卡包数量为dp[x]
dp[x] = (dp[x - A] + dp[x - A + 1] + … + dp[x - B]) / (B - A + 1) + 1
可以很直接的算出所有的期望

但是当A = 0的时候，等式两边都含有dp[x]，但是并不影响其正确性，只需要解方程即可。

代码

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

double dp[maxn], pre[maxn];

int main(){
	int n, l, r;
	cin >> n >> l >> r;

	dp[0] = 1; pre[0] = 1;
	if(l == 0){
		for(int i = 1 ; i <= n ; i++){
			dp[i] = (pre[max(0,i - l - 1)] - pre[max(0, i - r - 1)] + r - l + 1) / (r - l) ;
			pre[i] = pre[i - 1] + dp[i];
		}
	}
	else{
		for(int i = 1 ; i <= l ; i++)dp[i] = 1, pre[i] = pre[i - 1] + dp[i];
		for(int i = l + 1 ; i <= n ; i++){
			dp[i] = (pre[i - l] - pre[max(0, i - r - 1)]) / ( r - l + 1 ) + 1;
			pre[i] = pre[i - 1] + dp[i];
		}
	}
	printf("%.5f",dp[n]);
}

本文地址：https://blog.csdn.net/qq_35068676/article/details/110132906