lightoj 1030 概率dp

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

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

const int maxn = 105;
const int INF = 0x3f3f3f3f;

double dp[maxn];
int a[maxn];

int main()
{
    //freopen("E:\acm\input.txt","r",stdin);
    int T;
    cin>>T;
    for(int cas=1;cas<=T;cas++){
        int N;
        cin>>N;
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(int i=N-1;i>=1;i--){
            int k = min(N-i,6);
            for(int j=1;j<=k;j++)
                dp[i] += dp[i+j]+a[i+j];
            dp[i] /= k;
        }
        dp[1] += a[1];
        printf("Case %d: %.6lf
",cas,dp[1]);
    }
}

 //dp[i] 表示i位置以后期望得到的gold数。