题目大意:
有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的代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define INF 10000000
using namespace std;
int main()
{
int n,f;
double dp[];
int c[],t[];
while(scanf("%d %d",&n,&f)!=EOF)
{
int sum=,Max=-INF;
for(int i=; i<n; i++)
{
scanf("%d",&c[i]);
Max=max(Max,c[i]);
int tt=(int)((1.0+sqrt(5.0))/2.0*c[i]*c[i]);
t[i]=tt;
sum+=t[i];
}
double p=1.0/n;
for(int i=Max+; i<=*Max; i++)
dp[i]=(double)sum*p;
for(int j=Max; j>=f; j--)
{
double tem=0.0;
for(int i=; i<n; i++)
{
if(c[i]<j)
tem+=t[i]*p;
else
tem+=(+dp[j+c[i]])*p;
}
dp[j]=tem;
}
printf("%.3lf\n",dp[f]);
}
return ;
}
AC 代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define INF 10000000
using namespace std;
int main()
{
int n,f;
double dp[];
int c[],t[];
while(scanf("%d %d",&n,&f)!=EOF)
{
double sum=;
int Max=-INF;
for(int i=;i<n;i++)
{
scanf("%d",&c[i]);
Max=max(Max,c[i]);
int tt=(int)((1.0+sqrt(5.0))/2.0*c[i]*c[i]);
t[i]=tt;
sum+=t[i];
}
double p=1.0/n;
for(int i=Max+;i<=*Max;i++)
dp[i]=sum*p;
for(int j=Max;j>=f;j--)
{
double tem=0.0;
for(int i=;i<n;i++)
{
if(c[i]<j)
tem+=t[i]*p;
else
tem+=(+dp[j+c[i]])*p;
}
dp[j]=tem;
}
printf("%.3lf\n",dp[f]);
}
return ;
}