ZOJ Problem Set

题目大意:

有n条路，选每条路的概率相等，初始能力值为f,每条路通过的难度值为ci,当能力值大于某条路A的难度值b时，能够成功逃离，花费时间ti,小于等于时，不能逃离，天数加一天，但能力值增加b.

给定初始的能力值，求成功逃离的期望。

分析：

概率dp做的少，感觉不是很简单。

设dp[j]表示能力值为j时，逃离的期望值。

对于每条路i,当j>c[i]时，成功逃离+(ti[i]*p),否则加(+1+dp[j+c[j]])*p;

从后往前递推，求出dp[f]。

精度卡的好严，看看下面2个代码就行了

WA的代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<iostream>
 6 #define INF 10000000
 7 using namespace std;
 8 int main()
 9 {
10     int n,f;
11     double dp[100000];
12     int c[100000],t[100000];
13     while(scanf("%d %d",&n,&f)!=EOF)
14     {
15         int sum=0,Max=-INF;
16         for(int i=0; i<n; i++)
17         {
18             scanf("%d",&c[i]);
19             Max=max(Max,c[i]);
20             int tt=(int)((1.0+sqrt(5.0))/2.0*c[i]*c[i]);
21             t[i]=tt;
22             sum+=t[i];
23         }
24         double p=1.0/n;
25         for(int i=Max+1; i<=2*Max; i++)
26             dp[i]=(double)sum*p;
27         for(int j=Max; j>=f; j--)
28         {
29             double tem=0.0;
30             for(int i=0; i<n; i++)
31             {
32                 if(c[i]<j)
33                     tem+=t[i]*p;
34                 else
35                     tem+=(1+dp[j+c[i]])*p;
36             }
37             dp[j]=tem;
38         }
39         printf("%.3lf
",dp[f]);
40     }
41     return 0;
42 }

AC 代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<iostream>
 6 #define INF 10000000
 7 using namespace std;
 8 int main()
 9 {
10     int n,f;
11     double dp[100000];
12     int c[100000],t[100000];
13     while(scanf("%d %d",&n,&f)!=EOF)
14     {
15         double sum=0;
16         int Max=-INF;
17         for(int i=0;i<n;i++)
18         {
19             scanf("%d",&c[i]);
20             Max=max(Max,c[i]);
21             int tt=(int)((1.0+sqrt(5.0))/2.0*c[i]*c[i]);
22             t[i]=tt;
23             sum+=t[i];
24         }
25         double p=1.0/n;
26         for(int i=Max+1;i<=2*Max;i++)
27             dp[i]=sum*p;
28         for(int j=Max;j>=f;j--)
29         {
30             double tem=0.0;
31             for(int i=0;i<n;i++)
32             {
33                 if(c[i]<j)
34                     tem+=t[i]*p;
35                 else
36                     tem+=(1+dp[j+c[i]])*p;
37             }
38             dp[j]=tem;
39         }
40         printf("%.3lf
",dp[f]);
41     }
42     return 0;
43 }