題目大意：給定n個(gè)事件，第i個(gè)事件發(fā)生的概率為pi，收益為ai，初始收益為k，求n個(gè)事件之后發(fā)生的事件數(shù)>=l且收益>=0的概率

收益只可能是正整數(shù)或-1。

Solution

dp[i][j][k]表示前i個(gè)時(shí)間，發(fā)生了j個(gè)，得分為k的概率。

顯然這三位對(duì)答案都是有用的，缺一不可。

這題需要一些trick。

當(dāng)與出題人心有靈犀之后。。。觀察到最后只需要>=0，而每個(gè)事件權(quán)值最小是-1，所以我們給第三維卡一個(gè)n的上限就好了。

Code

#include<iostream> #include<cstdio> #define f(i,j,k) dp[i][j][k+200] using namespace std; const double eps=1e-14; double dp[202][202][402],p[202],ans; int n,m,l,a[202]; int main(){scanf("%d%d%d",&n,&l,&m);for(int i=1;i<=n;++i)scanf("%lf",&p[i]),p[i]/=100.000;for(int i=1;i<=n;++i)scanf("%d",&a[i]);f(0,0,min(n,m))=1;for(int i=1;i<=n;++i)for(int j=0;j<i;++j)for(int k=-n;k<=n;++k)if(f(i-1,j,k)>=eps){f(i,j,k)+=f(i-1,j,k)*(1.000-p[i]);f(i,j+1,min(n,k+a[i]))+=f(i-1,j,k)*p[i]; }for(int i=l;i<=n;++i)for(int j=0;j<=n;++j)ans+=f(n,i,j);printf("%.6lf",ans);return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZH-comld/p/9588211.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3029守卫者的挑战（概率dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。