[BZOJ 4008][HNOI2015]亚瑟王：期望DP

本文主要是介绍[BZOJ 4008][HNOI2015]亚瑟王：期望DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

f[i][j]表示第i张卡在第j回合被轮到（但不一定发动）的概率。
f[i][j]= f[i-1][j] * ( 1-p[i-1] ) ^ j + f[i-1][j+1] * ( 1- ( 1-p[i-1] ) ^ ( j+1 ) ) ,ans+=f[i][j] * ( 1 - ( 1 - p[i] ) ^ j ) * d[i]。

/*
User:Small
Language:C++
Problem No.:4008
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
double f[225][140],p[225],ans;
int n,r,d[225];
void solve(){memset(f,0,sizeof(f));scanf("%d%d",&n,&r);for(int i=1;i<=n;i++)scanf("%lf%d",&p[i],&d[i]);f[0][r]=1;ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=r;j++){f[i][j]=f[i-1][j]*pow(1-p[i-1],j)+f[i-1][j+1]*(1-pow(1-p[i-1],j+1));ans+=f[i][j]*(1-pow(1-p[i],j))*d[i];}}printf("%.10lf\n",ans);
}
int main(){freopen("data.in","r",stdin);//int t;scanf("%d",&t);while(t--) solve();return 0;
}

这篇关于[BZOJ 4008][HNOI2015]亚瑟王：期望DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---