[Light OJ]Discovering Gold（期望DP）

传送门：Discovering Gold | LightOJ

题目描述 / Problem

在一个一维数轴上，起始点为1，终点为N。

从起始点开始，每次可以掷骰子，等概率地往后走[1, 6]中的任意距离，如果下一个点超过了N，重新掷骰子，每个点有一个金币数a[i]。求到达终点的金币期望。

思路 / Thought

期望DP。

第一种思路，是对从起始点到达该点的概率进行dp，然后乘以各点的金币数就是期望。

从前往后就可以。

为什么乘以各点金币数呢？因为这里是对概率的dp，也就是说相当于到了第i个点dp[i]次。

代码一

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 107;
double dp[maxn];//dp[i] means the expectation of possibility from 1 to i
int a[maxn];//the gold on the Point[i]


void solve()
{
	int N;cin >> N;//there are N points on the array
	
	for(int i = 1;i <= N; ++ i)cin >> a[i];//input
	
	memset(dp, 0, sizeof(int) * (N + 1));//init the dp array
	dp[1] = 1.0;//init
	
	for(int i = 1;i <= N; ++ i)
	{
		int k = min(N - i, 6LL);//the possibilities you can go
		for(int j = 1;j <= k; ++ j)//jump j steps every time
			dp[i + j] += dp[i] * 1.0 / k;
	}
	double ans = 0;
	for(int i = 1;i <= N; ++ i)ans += dp[i] * a[i];
	cout << fixed << setprecision(6) << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	int _;cin >> _;
	for(int i = 1;i <= _; ++ i)
	{
		cout << "Case " << i << ": "; 
		solve();
	}
	return 0;
}

第二种思路，从后往前DP，dp[i]表示从i走到N的金币期望，这里最后不需要计算概率因为概率为1。

状态转移方程：

代码二

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int maxn = 109;
double dp[maxn];
int a[maxn];
int kase = 1;

void solve()
{
	int N;cin >> N;
	memset(dp, 0, sizeof(int) * (N + 1));
	
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	
	for(int i = N;i >= 1; -- i)
	{
		dp[i] = a[i];
		int k = min(N - i, 6LL); //k表示可以往后走的格子数
		for(int j = 1;j <= k; ++ j)
			dp[i] += dp[i + j] * 1.0 / k;
	}
	printf("Case %lld: %lf\n",kase ++, dp[1]);
}

signed main()
{
	int T;cin >> T;
	while(T --)solve();	
	return 0;
}