专栏文章

ABC382-E 题解

刘刘梓轩2010
AT_abc382_e题解参与者 7已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miqx9swd
此快照首次捕获于
2025/12/04 12:14
3 个月前
此快照最后确认于
2025/12/04 12:14
3 个月前
查看原文

题意

你有无数包卡牌，每包有 nn 张，同时有 nn 种稀有卡牌，每张稀有卡牌在每包中出现的概率为 pip_i，问期望拆多少包卡牌可以获得 mm 张稀有卡牌。
n≤5000n \le 5000，m≤5000m \le 5000。

思路

很显然，我们可以用 dp 解决这个问题。
设 fif_i 为至少获得 ii 张稀有卡牌的期望拆的包数，gig_i 为每包恰好获得 ii 张卡牌的概率。
我们首先求解 gg，我们可以考虑新加进来一种稀有卡牌，设新加进来第 ii 种稀有卡，考虑转移 gjg_j，那么有两种情况，一种是前 i−1i-1 种卡牌已经拆出 jj 张的概率，另一种是前 i−1i-1 种卡牌拆出 j−1j-1 张，同时拆出来了第 ii 种的概率，于是转移方程为 gj=gj×(1−pi)+gj−1×pig_j=g_j\times (1-p_i)+g_{j-1}\times p_i。类似于背包，要倒序转移。
再来求解 ff。转移时，我们可以枚举这一次拆出来的数量，借助 gg 转移。要让总卡牌数至少为 ii，如果这一包拆出 jj 张，则原来至少有 max⁡{0,i−j}\max\{0,i-j\} 张。方程即为 fi=1+∑j=0nfmax⁡{0,i−j}×gjf_i=1+\sum_{j=0}^n f_{\max\{0,i-j\}}\times g_j。
这样还有个问题，fif_i 会从自己转移过来，只需要把右边带 fif_i 的项移到右边即可。
最终的式子即为 fi=11−g0×(1+∑j=1nfmax⁡{0,i−j}×gj)f_i=\tfrac{1}{1-g_0}\times(1+\sum_{j=1}^n f_{\max\{0,i-j\}}\times g_j)。
不理解可以结合代码食用。

Code

C
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=5000+10;
const int inf=0x3f3f3f3f3f3f3f3f;
double g[N];
double f[N];
int n,x;
double p[N],ans;
signed main()
{
	//freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	{
	    cin>>p[i];
	    p[i]/=100;
    }
    g[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=n;j>=1;j--)
        {
            g[j]=g[j]*(1-p[i])+g[j-1]*p[i];
        }
        g[0]*=(1-p[i]);
    }
    for(int i=1;i<=x;i++)
    {
        f[i]=1;
        for(int j=1;j<=n;j++)
        {
            f[i]+=f[max(0ll,i-j)]*g[j];
        }
        f[i]/=(1-g[0]);
    }
    printf("%.8lf",f[x]);
    return 0;
}

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...