zoj 3640 Help Me Escape （機率dp）

題意： 吸血鬼被困在山洞中 這裡有n條出去的路每條路有一個攻擊力c[i]  現在吸血鬼每天随機選一天路 當吸血鬼p的攻擊力大于c[i]時吸血鬼可以花ti的時間從這條路逃出去 如果p小于c[i]那麼吸血鬼就得花一天時間讓自己的攻擊力增加ci然後再随機選一個路 問吸血鬼最後出去時天數的期望

題目連結：點選打開連結

//記憶化搜尋
#include<stdio.h>
#include<string.h>
#include<math.h>

double dp[21000];//dp[i]存吸血鬼的攻擊力為i時吸血鬼逃出去的期望天數
int c[200];

int n;
double dfs(int p)
{
    if(dp[p]>1e-12)return dp[p];
    double ans=0;
    int i;
    for(i=1;i<=n;i++)
    {
       if(p>c[i]) ans+=1.0/n*(int)((1.0+sqrt(5.0))/2*c[i]*c[i]); // 吸血鬼的攻擊力大于ci 不明白為什麼要取整
       else ans+=1.0/n*(dfs(p+c[i])+1);// 吸血鬼的攻擊力小于ci
    }
    return dp[p]=ans;
}

int main()
{
    int p;
    while(scanf("%d%d",&n,&p)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        int i;
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        double ans=dfs(p);
        printf("%.3f\n",ans);
    }
    return 0;
}