简单概率dp-hdu-4487-Maximum Random Walk
题目大意:
开始位置在0,每一步可以向右向左或者不动,问走了n步后,路径中能到达最右的期望。
解题思路:
比赛的时候,题目理解错了,认为要回到起点。-_- -_-
由于最后到达的位置不确定,每条路径的最右距离也不确定。
所以记dp[i][j][k]为走了i步,到达j位置,且路径中最右位置为k时概率。
显然k>=j 否则为0
如果k==j,这一步有两种情况,1、刚好第一次达到最大 2、先前已经达到了最大。注意此时不能从右边向左过来,超过了k.
如果k>j ,说明这一步没有到达k,只能是前面的已经到达了k.
s为不动的概率,r,l分别为向右走和向左走的概率。
记开始的位置为100.
代码:
<SPAN style="FONT-SIZE: 18px">#include<iostream> #include<cmath> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #define eps 1e-6 #define INF 0x1f1f1f1f #define PI acos(-1.0) #define ll __int64 #define lson l,m,(rt<<1) #define rson m+1,r,(rt<<1)|1 //#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; /* freopen("data.in","r",stdin); freopen("data.out","w",stdout); */ #define N 110 double dp[2][N*2][N*2]; //dp[][i][j]表示走到当前步,到达i,最右的位置为j的概率 int main() { int t,d,n; double l,r,s; scanf("%d",&t); while(t--) { scanf("%d%d%lf%lf",&d,&n,&l,&r); s=1-l-r; memset(dp,0,sizeof(dp)); dp[0][100][100]=1; //初始化最开始的位置 int la=0,cur; for(int i=1;i<=n;i++) { cur=la^1; for(int j=100-i;j<=100+i;j++) { for(int k=max(100,j);k<=200;k++) //k肯定要>=j,第一步在100无论怎么走最右肯定大于等100 { if(k==j) //这一步到了最右 dp[cur][j][k]=dp[la][j][k]*s+dp[la][j-1][k-1]*r+dp[la][j-1][k]*r; else //k>j的情况 之前已经到达了最大k dp[cur][j][k]=dp[la][j][k]*s+dp[la][j-1][k]*r+dp[la][j+1][k]*l; } } la=cur; } double ans=0; for(int i=(100-n);i<=100+n;i++) for(int j=100;j<=100+n;j++) ans=ans+dp[cur][i][j]*(j-100); //直接求期望 printf("%d %.4lf\n",d,ans); } return 0; } </SPAN>
补充:软件开发 , C++ ,