【LightOJ 1030 ?Discovering Gold】概率期望DP

LightOJ 1030 ?Discovering Gold

题意

从左到右有$n$个方格，每一块方格上有$x_i$块黄金，最初站在第一块方格上，有一个$6$个面的均匀骰子，每一个面上的权值是$1?6$，每次掷骰子之后按照点数$y$跳到$y$步之后的方格，如果超出范围，则重新掷骰子，问到达第n个方格能得到的期望黄金数。

做法

从后往前求期望，设dp[i]为i点到达n能获得的期望黄金数，那么首先dp[n]=x[n]，之后每个方格的dp值就是所有他能到达的方格的dp值的平均值加上当前点的黄金数,最后dp[1]就是答案。

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5+5;
double a[maxn];
int main()
{
    int t;int tt=0;scanf("%d",&t);while(t--){
    int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lf",&a[i]);for(int i=n-1;i>=1;i--){
    double tmp=0.0;int cnt=0;for(int j=1;j<=6;j++){
    if(i+j<=n){
    cnt++;tmp+=a[i+j];}}a[i]+=tmp/cnt;}printf("Case %d: %.10f\n",++tt,a[1]);}return 0;
}