題意：
一只吸血鬼，有n條路給他走，每次他隨機走一條路，
每條路有個限制，如果當時這個吸血鬼的攻擊力大于
等于某個值，那么就會花費t天逃出去，否則，花費1天
的時間，并且攻擊力增加，問他逃出去的期望

用記憶化搜索做，很好理解。

1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const double eps=1e-5; 11 #define cl(a) memset(a,0,sizeof(a)) 12 #define sc(a) scanf("%d",&a); 13 #define scc(a,b) scanf("%d%d",&a,&b); 14 #define ts printf("*****\n"); 15 const int MAXN=200010; 16 int c[110]; 17 double dp[MAXN]; 18 int n,m,tt; 19 double dfs(int p) 20 { 21 if(dp[p]>0) return dp[p]; 22 dp[p]=0; 23 for(int i=0;i<n;i++) 24 { 25 if(p>c[i]) 26 { 27 double temp=(1.0+sqrt(5))/2*c[i]*c[i]; 28 int t=(int)temp; 29 dp[p]+=(double)t/n; 30 } 31 else 32 { 33 dp[p]+=(dfs(p+c[i])+1)/n; 34 } 35 } 36 return dp[p]; 37 } 38 int main() 39 { 40 int i,j,k,f; 41 #ifndef ONLINE_JUDGE 42 freopen("1.in","r",stdin); 43 #endif 44 while(scanf("%d%d",&n,&f)!=EOF) 45 { 46 for(i=0;i<n;i++) sc(c[i]); 47 cl(dp); 48 printf("%.3lf\n",dfs(f)); 49 } 50 }

?

轉載于:https://www.cnblogs.com/cnblogs321114287/p/4421329.html

總結

以上是生活随笔為你收集整理的zoj 3640 概率dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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