LightOJ - 1030 期望+dp

题目链接：https://vjudge.net/problem/25907/origin

一个山洞，里面有有1到n个位置，每个位置都有一定的金币，你有一个六面的骰子，一开始你在1，每次摇到了哪个数就往前走几步

如果超过了n就重新摇，知道n为止，问你到n需要摇的次数的期望。

一开始我用正推，一直错，在这里我们需要逆推，我们先不想正推，等下再说。

我们假设Ei表示i点开始可以获得的金子的期望，如果i点到n的距离>=6,那么Ei=(E(i+1)/6+E(i+2)/6+E(i+3)/6+...+E(i+6)/6).

如果距离<6,Ei=(E(i+1)/6+E(i+2)/6+E(i+3)/6+...+En/6).注意：逆推时每个E的概率都是一样的。

#include<stdio.h>

int n,m,k,t;

double dp[];

int min(int a,int b)

{

    if(a<b)

    return a;

    return b;

}

int main()

{

    scanf("%d",&t);

    int count=;

    while(t--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

        scanf("%lf",&dp[i]);

        for(int i=n-;i>=;i--)

        {

            int num=min(n,i+);

            double sum=;

            for(int j=i+;j<=num;j++)

            {

                sum+=dp[j];

            }

            dp[i]=sum/(num-i)+dp[i];

        }

        printf("Case %d: %.7f\n",++count,dp[]);

    }

    return ;

}

为什么不能正推，现在给出我学长的解释，感觉很有道理：

为什么只有从后往前才会符合推理
因为从前往后的概率分布是不均匀的。
从a[i-6]到a[i]的概率并不是1/6，因为a[i-6]可以先到a[i-5]，再到a[i]，

所以实际上，a[i-6]到a[i]的 概率是低于其他值的，因为其他值到a[i]的概率是要先算上a[i-6]没有成功抵达a[i]的概率。

 不能以1开始，因为状态方程只能为
a[i]=1/6*a[i+1]+ 1/6*a[i+2]+……+1/6*a[i+6]
假如我们令方程为
a[i]=1/6*a[i-1]+ 1/6*a[i-2]+……+1/6*a[i-6]
a[2]=a[1]+a[2]
a[3]=0.5a[1]+0.5a[2]+a[3]=a[1]+0.5a[2]+a[3]
那么
a[4]=1/3a[1]+1/3a[2]+1/3a[3]+a[4]=a[1]+0.5a[2]+1/3a[3]+a[4]
然而实际上a[4]的期望并不是这样
如果1到4。
从1开始，到2的概率为1/3，到3的概率为1/3加上2到3的概率，为0.5。
所以正确的是a[4]=a[1]+1/3a[2]+0.5a[3]+a[4]。