Aeroplane chess

HDU - 4405

大致题意:

有0-n一共n+1个坐标,起始点在0,靠扔骰子决定前进几格,骰子一共六个面,标有1,2,3,4,5,6,每一面的概率相同,另外给出m条边,表示a点可以直接到b点.只要点数>=n就结束

求最后结束扔骰子次数的期望

---

解题思路:

概率dp求期望一般是逆推

状态表示:f[i] 表示从i位置走到 >=n位置需要的次数期望

初始化 f[n]=0, f[0] 为答案

分析: f[i]有俩种状态转移:

----------f[i+j] 其中j=1,2,3,4,5,6 概率: 1/6

----------f[g[i]] 直接从i点到g[i]点 概率: 1

状态方程:略~

补充:本人提前处理出>n的情况 还可以把>n的点当成n点看待,没结果一样

---

AC代码:

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define debug(a) cout << #a << " = " << a << endl;
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m;
double f[N]; 
int g[N];
int main(void)
{
	while (scanf("%d%d", &n, &m), n + m) {
		for (int i = 0; i <= n; ++i) f[i] = 0, g[i] = -1;

		while (m--) {
			int a, b; scanf("%d%d", &a, &b);
			g[a] = b;
		}
		for (int i = n; i <= n + 6; ++i)f[i] = 0; //初始化>=n的所以情况
		for (int i = n - 1; i >= 0; --i) {
			if (g[i] != -1)f[i] = f[g[i]];
			else {
				f[i]++;
				for (int j = 1; j <= 6; ++j)
					f[i] += 1.0 / 6 * f[i + j];
			}
		}
		printf("%.4f\n", f[0]);
	}
	return 0;
}

---