hdu 4576 Robot(简单的概率DP)

题意：

给你一个环，最开始机器人站在1的位置，现在有m条指令，每次顺时针或者逆时针的走x步，现在问你停留在l到r区间的概率。

题解：

考虑dp[i][j]，表示前i个操作停留在j这个位置的概率，那么转移方程就为dp[i][j]=0.5*(dp[i-1][j-x]+dp[i-1][j+x]);

然后用滚动数组优化一下就行。复杂度n*m，需要加一个读入优化才能卡过去。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int BUF=40000000;
 6 char Buf[BUF],*buf=Buf;
 7 
 8 inline void read(int&a){for(a=0;*buf<48;buf++);while(*buf>47)a=a*10+*buf++-48;}
 9 
10 int n,m,l,r,x;
11 double dp[2][220];
12 
13 int main(){
14     fread(Buf,1,BUF,stdin);
15     while(1)
16     {
17         read(n),read(m),read(l),read(r);
18         if(!(n+m+l+r))break;
19         int now=0;
20         dp[0][0]=1;
21         F(i,1,n-1)dp[i][0]=0;
22         F(i,1,m)
23         {
24             read(x);
25             F(j,0,n-1)dp[now^1][j]=0.5*(dp[now][(j+x)%n]+dp[now][(j-x+n)%n]);
26             now^=1;
27         }
28         double ans=0;
29         F(i,l-1,r-1)ans+=dp[now][i];
30         printf("%.4f
",ans);
31     }
32     return 0;
33 }

View Code