首页 > 代码库 > HDU 4405 Aeroplane chess 概率dp

HDU 4405 Aeroplane chess 概率dp

2024-07-28 02:02:23   220人阅读

题目大意：
 
跳棋有0~n个格子，每个格子X可以摇一次色子，色子有六面p(1=<p<=6),概率相等，可以走到X+p的位置，有些格子不需要摇色子就可以直接飞过去。问从0出发到达n或超过n摇色子的次数的期望。
（copy的
思路：
先处理一下每个点最远能飞到的点
保证只会往终点的方向飞。。

能确定的状态就是最终n-n+5这6个点的步数是0
然后从后往前递推
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
template <class T>
inline bool rd(T &ret) {
    char c; int sgn;
    if(c=getchar(),c==EOF) return 0;
    while(c!='-'&&(c<'0'||c>'9')) c=getchar();
    sgn=(c=='-')?-1:1;
    ret=(c=='-')?0:(c-'0');
    while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
    ret*=sgn;
    return 1;
}
template <class T>
inline void pt(T x) {
    if (x <0) {
        putchar('-');
        x = -x;
    }
    if(x>9) pt(x/10);
    putchar(x%10+'0');
}
using namespace std;
typedef long long ll;
const int N = 100010;
int n, m;
double dp[N];
int to[N];
double solve(){
	for(int i = 0; i < 6; i++)
		dp[i+n] = 0;
	for(int i = n-1; i >= 0; i--)
	{
		if(to[i]!=-1)
			dp[i] = dp[to[i]];
		else {
			dp[i] = 1.0;
			for(int j = 1; j <= 6; j++)
				dp[i] += dp[i+j] / 6.0;
		}
	}
	return dp[0];
}
void input(){
	memset(to, -1, sizeof to);
	while(m--){
		int x, y;rd(x); rd(y);
		to[x] = y;
	}
	for(int i = n-1; i >= 0; i--){
		if(to[i] == -1)continue;
		if(to[to[i]] != -1)
		to[i] = to[to[i]];
	}
}
int main() {
	while(cin>>n>>m, n+m){
		input();
		printf("%.4f\n", solve());
    }
    return 0;
}
/*


*/


HDU 4405 Aeroplane chess 概率dp


联系
我们