[HNOI2015]亚瑟王

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题面在这里

题意

\(n\)张卡按照一定顺序排列，每轮从第\(1\)张开始考虑到最后一张，考虑一张卡时有\(p[i]\)的概率产生\(d[i]\)的贡献，产生贡献时直接退出该轮并在之后的考虑中直接跳过，若不产生贡献继续考虑下一张直到产生贡献或所有牌被考虑完时结束该轮，求期望贡献。多组数据，\(T<=444\)。

sol

刚了整整一下午还是看了题解(膜拜秒切的大佬orz)

如果直接按照轮数来DP的话每张牌无论是产生贡献的时间还是顺序都需要考虑，原地爆炸

所以考虑每一张牌对答案产生的贡献

而其实第\(i\)张牌在\(r\)轮中产生贡献的概率只和前\(i-1\)张牌在\(r\)轮中产生贡献的数量(假设为\(j\))有关

因为无论这\(j\)张牌产生贡献的时间和顺序怎样变化,最后都一定会有\((r-j)\)轮考虑到第\(i\)张牌

如果设前\(i-1\)张牌在\(r\)轮中\(j\)张产生贡献的概率为\(f[i-1][j]\),那么第\(i\)张牌产生贡献的概率(假设为\(g[i]\))就可以计算了:$$g[i]=\sum_{j=0}^{{min(i,r)}{f[i-1][j]*(1-(1-p[i])}{r-j})}$$

最后$$Ans=\sum_{i=1}^{n}{(g[i]*d[i])}$$

那么\(f[i][j]\)怎么计算呢? 从前往后递推:$$f[i][j]=f[i-1][j]*(1-p[i])^{{r-j}[j<=i-1]+f[i-1][j-1]*(1-(1-p[i])}{r-j+1})[j>0]$$

代码

#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define pb push_back
#define RG register
#define il inline
using namespace std;
const int mod=1e9+7;
const int N=225;
const int R=135;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}int T,n,r,d[N];
dd p[N],pw[N][R];
il void init(int n,int r){
for(RG int i=1;i<=n;i++){
dd s=1-p[i];pw[i][0]=1;
for(RG int j=1;j<=r;j++)
pw[i][j]=pw[i][j-1]*s;
}
}dd f[N][N];
il void DP(){
f[0][0]=1;
for(RG int i=1;i<=n;i++)
for(RG int j=0;j<=min(i,r);j++){
f[i][j]=f[i-1][j]*pw[i][r-j];
if(j)f[i][j]+=f[i-1][j-1]*(1-pw[i][r-j+1]);
}
}il void solve(){
RG dd ans=0;
for(RG int i=1;i<=n;i++){
RG dd sum=0;
for(RG int j=0;j<=min(i-1,r);j++)
sum+=(1-pw[i][r-j])*f[i-1][j];
ans+=sum*d[i];
}
printf("%.10lf\n",ans);
}int main()
{
T=read();
while(T--){
n=read();r=read();
for(RG int i=1;i<=n;i++)scanf("%lf%d",&p[i],&d[i]);
init(n,r);DP();solve();
}
return 0;
}