hdu4576 Robot

发表于 | 更新于 | 分类于

题意

​ 在一个环形区域里面分成n个部分，初始在第一个部分(顺时针1到n)，截下来有m次操作，每次可以顺势针或者逆时针走a步问最后走在l到r这个区域内的概率是多少？

思路

​ 一道标准的概率dp题，每次走路都由上一步推导而来，只需要将上一步所走的路存起来,最后再把l到r这个区间所有的概率加起来即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
using namespace std;
double dp[2][210];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m,l,r;
	while(cin>>n>>m>>l>>r&&n+m+l+r){
		int t=0;
		for(int i=0;i<=n;i++) dp[0][i]=0;
		dp[0][0]=1;
		while(m--){
			int x;
			cin>>x;
			for(int i=0;i<n;i++) dp[t^1][i]=0;
			for(int i=0;i<n;i++){
				if(dp[t][i]){
					dp[t^1][(i+x)%n]+=0.5*dp[t][i];
					dp[t^1][(i-x+n)%n]+=0.5*dp[t][i];
				}
			}
			t^=1;
		}
		double ans=0;
		for(int i=l-1;i<=r-1;i++){
			ans+=dp[t][i];
		}
		printf("%.4lf\n",ans);
	}
}