/*
dp[i]表示力量为i时的期望
dp[i]=sum{tj}/n+sum{dp[i+cj]+1}/n //前一项是cj<i的和，后一项是cj>=i的和
初始状态dp[m]
*/
#include<bits/stdc++.h>
using namespace std;
const double C = ((
double)
1+sqrt(
5))/
2;
const double esp = 1e-
8;
const int maxn = 3e4+
5;
int n,f,c[maxn],Max;
double dp[maxn];
int main(){
while(scanf(
"%d%d",&n,&f)!=
EOF){
Max=
f;
memset(dp,0,
sizeof dp);
for(
int i=
1;i<=n;i++)scanf(
"%d",&c[i]),Max=
max(Max,c[i]);
for(
int i=
1;i<=n;i++
)
dp[Max+
1]+=(
double)((
int)(C*c[i]*c[i]))/
n;
for(
int i=Max+
2;i<=
2*Max;i++)dp[i]=dp[Max+
1];
for(
int i=Max;i>=f;i--
){
for(
int j=
1;j<=n;j++
)
if(i>c[j])
//直接可以走出去
dp[i]+=(
double)((
int)(C*c[j]*c[j]))/
n;
else
dp[i]+=(dp[i+c[j]]+
1)/
n;
}
printf("%.3lf\n",dp[f]);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11042811.html
