首页 > 代码库 > BZOJ 1426 收集邮票 ——概率DP
BZOJ 1426 收集邮票 ——概率DP
$f(i)$表示现在有$i$张，买到$n$张的期望
所以$f(i)=f(i+1)+\frac {n}{n-i}$
费用提前计算，每张邮票看做一元，然后使后面每一张加1元
$g(i)$表示当前为$i$张期望到$n$张时花掉的钱。
那么$g(i)=g(i+1)+f(i+1)+\frac{i}{n-i}f(i)+\frac{n}{n-i}$
递推即可
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
double f[10005],g[10005],nn;int n;
int main()
{
scanf("%d",&n); nn=n;
D(i,n-1,0) f[i]=f[i+1]+nn/(nn-i);
D(i,n-1,0) g[i]=g[i+1]+f[i+1]+i/(nn-i)*f[i]+nn/(nn-i);
printf("%.2f\n",g[0]);
}
BZOJ 1426 收集邮票 ——概率DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。