hdu 4405 Aeroplane chess

Problem

acm.hdu.edu.cn/showproblem.php?pid=4405

vjudge.net/contest/151678#problem/R

Reference

bbs.csdn.net/topics/380193920（C++控制小数位数）

Meaning

一行格子编号从 0 到 n，开始在 0 号格，每次掷骰子（1 ~ 6），投到多少就向前走多少步；有些格上有飞机，可以带他走到后面的某个点，如果那个点又有飞机，就可以连飞（被带飞时不用掷骰子）。求走到或超过第 n 格要掷骰子的次数的期望。

Analysis

dp[i]：到了 i 号格后，为达目标仍需掷骰子的期望次数。

dp[i] = {

    ( dp[i+1] + dp[i+2] + … + dp[i+6] ) / 6 + 1，i 号格没飞机；

    dp[j]，i 号格有飞机，且最终飞到 j 号格

}

顺便学了一波C++控制小数位数的方法…

Code

#include <cstring>
#include <iostream>
#include <iomanip>
using namespace std;
const int N = 100000, M = 1000;

int jp[N+1];
double dp[N+6];

int main()
{
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	cout.precision(4);
	int n, m;
	while(cin >> n >> m, n||m)
	{
		memset(jp, 0, sizeof jp);
		for(int i=0, x, y; i<m; ++i)
		{
			cin >> x >> y;
			jp[x] = y;
		}
		for(int i=n-1; ~i; --i)
			if(jp[i] && jp[jp[i]])
				jp[i] = jp[jp[i]];
		for(int i=n; i<n+6; ++i)
			dp[i] = 0.0;
		for(int i=n-1; ~i; --i)
			if(jp[i])
				dp[i] = dp[jp[i]];
			else
			{
				dp[i] = 0.0;
				for(int j=1; j<=6; ++j)
					dp[i] += dp[i+j];
				dp[i] /= 6.0;
				dp[i] += 1.0;
			}
		cout << dp[0] << '\n';
		/* 或者这样输出：
		 * cout << setiosflags(ios::fixed) <<
		 * 			setprecision(4) << dp[0] << '\n';
		 */
	}
	return 0;
}