HDU 4405 / Aeroplane chess

Posted on By 二价氢

题目:HDU 4405

一直线,每次掷骰子决定向前走步,同时直线上有若干跳跃点,位于的跳跃点,可向前跳到上,跳到位置或之后的位置算作胜利,问胜利所需跳跃步数的期望。

数位DP,我仍是算贡献做的

AC-Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 10;
const double six = 1.0 / 6;
double p[maxn] , e[maxn];
int fa[maxn];
int n , m;
int getfa(int x)
{
	return fa[x] == x ? x : fa[x] = getfa(fa[x]);
}
void unionfa(int x , int y)
{
	fa[getfa(x)] = y;
}
bool read()
{
	scanf("%d%d" , &n , &m);
	memset(p , 0 , sizeof(p));
	memset(e , 0 , sizeof(e));
	if (n == 0)
		return false;
	for (int i = 0 ; i <= n + 6 ; i++)
		fa[i] = i;
	for (int i = n + 1 ; i <= n + 6 ; i++)
		unionfa(i , n);
	for (int i = 0 ; i < m ; i++)
	{
		int x , y;
		scanf("%d%d" , &x , &y);
		unionfa(x, y);
	}
	p[0] = 1;
	e[0] = 0;
	for (int i = 0 ; i < n ; i++)
	{
		for (int j = 1 ; j <= 6 ; j++)
		{
			int rj = getfa(i + j);
			p[rj] += p[i] * six;
			e[rj] += (e[i] + p[i]) * six;
		}
	}
	printf("%.4f\n" , e[n]);
	return true;
}
int main()
{
	while (read());
	return 0;
}