HDU4405 期望

对于期望，首先，对于这个公式中p表示概率，x表示随机变量

展开则为 ex= p1*x1+p2*x2+p3*x3.......

对于本题 假设 ex[ i ]表示当前 i 走到 n 的期望值。所以若 i 处没有飞机，ex[ i ]=sigma(1/6*ex[i+k])+1 其中(k=1...6) （+1表示掷了一次骰子） 若 i 处有飞机，则直接等于 ex[ j ]

结果则为 ex【0】

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 100005;
int fly[ maxn ];
double ex[ maxn ];
int main(){
    int n,m;
    while( scanf("%d%d",&n,&m)!=EOF ,n+m ){
        for( int i=0;i<=n;i++ ){
            ex[ i ]=0;
            fly[ i ]=-1;
        }
        for( int i=0;i<m;i++ ){
            int a,b;
            scanf("%d%d",&a,&b);
            fly[a]=b;
        }
        ex[ n ]=0;
        for( int i=n-1;i>=0;i-- ){
            if( fly[i]!=-1 ){
                ex[ i ]=ex[ fly[i] ];
            }
            else {
                for( int j=1;j<=6;j++ ){
                    if( i+j>=n )
                        ex[ i ]+=((1.0/6.0)*ex[ n ]);
                    else
                        ex[ i ]+=((1.0/6.0)*ex[ i+j ]);
                }
                ex[ i ]+=1.0;
            }
        }
        printf("%.4lf\n",ex[ 0 ]);
    }
    return 0;
}