loj 1030概率dp

题目链接：http://lightoj.com/volume_showproblem.php?problem=1030

思路：一直以来对这种概率题都挺感冒的=.=......还是说一下思路吧，dp[i]表示前i个位置所能能到的期望值，然后我们可以从后往前递推。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

const int MAXN = (100 + 10);
double dp[MAXN], num[MAXN];
int n;

int main()
{
    int _case, t = 1;
    scanf("%d", &_case);
    while (_case--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%lf", &num[i]);
        }
        memset(dp, 0, sizeof(dp));
        dp[n] = num[n];
        for (int i = n - 1; i >= 1; i--) {
            int d = min(6, n-i);
            dp[i] = num[i];
            for (int j = 1; j <= d; j++) {
                dp[i] += dp[i+j]/d;
            }
        }
        printf("Case %d: %.7lf
", t++, dp[1]);
    }
    return 0;
}