LightOJ

题意：t 组数据，每组给出 n 个数，代表 n 个格子的值，现在要从第一个格子出发前往第 n 个格子，每到达一个格子都能扔一次 1~6 的骰子，决定下一步走到哪个位置，若当前位置+骰子掷出的值>n 则重新掷骰子，直到到达第 n 个格子结束，问从最终获得格子上的值的期望值

题目链接

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 1e5+7;
int a[107];
double dp[107];
int main(){
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    int t;
    scanf("%d",&t);
    int w=0;
    while(t--){
        int n; scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            dp[i]=a[i];
        }
        for(int i=n;i>=1;i--){
            int top=min(6,n-i);
            for(int j=1;j<=top;j++)
                dp[i]=dp[i]+dp[i+j]*(1.0/top);
        }
        printf("Case %d: %.10f
",++w,dp[1]);
    }
}