zoj 3640 Help Me Escape 概率DP

记忆化搜索+概率DP
代码如下：
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #include<cmath>
 6 #include<cstring>
 7 #include<vector>
 8 #define ll __int64
 9 #define pi acos(-1.0)
10 #define MAX 50000
11 using namespace std;
12 int c[101],n,ff;
13 double dp[100001];
14 double solve(int f)
15 {
16     if(dp[f]>0) return dp[f];
17     dp[f]=0;
18     for(int i=0;i<n;i++){
19         if(f>c[i]){
20             double t=(sqrt(5.0)+1.0)/2*c[i]*c[i];
21             int p=(int)t;
22             dp[f]+=1.0*p/n;
23         }
24         else{
25             dp[f]+=(1+solve(f+c[i]))/n;
26         }
27     }
28     return dp[f];
29 }
30 int main(){
31     while(scanf("%d%d",&n,&ff)!=EOF){
32         for(int i=0;i<n;i++) cin>>c[i];
33         memset(dp,0,sizeof(dp));
34         printf("%.3lf
",solve(ff));
35     }
36 
37     return 0;
38 }
View Code