hdu4487 Maximum Random Walk (概率dp)
Maximum Random Walk
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 229 Accepted Submission(s): 128
Problem Description
Consider the classic random walk: at each step, you have a 1/2 chance of taking a step to the left and a 1/2 chance of taking a step to the right. Your expected position after a period of time is zero; that is, the average over many such random walks is that you end up where you started. A more interesting question is what is the expected rightmost position you will attain during the walk.
Input
The first line of input contains a single integer P, (1 <= P <= 15), which is the number of data sets that follow. Each data set should be processed identically and independently.
Each data set consists of a single line of input consisting of four space-separated values. The first value is an integer K, which is the data set number. Next is an integer n, which is the number of steps to take (1 <= n <= 100). The final two are double precision floating-point values L and R
which are the probabilities of taking a step left or right respectively at each step (0 <= L <= 1, 0 <= R <= 1, 0 <= L+R <= 1). Note: the probably of not taking a step would be 1-L-R.
Output
For each data set there is a single line of output. It contains the data set number, followed by a single space which is then followed by the expected (average) rightmost position you will obtain during the walk, as a double precision floating point value to four decimal places.
Sample Input
3
1 1 0.5 0.5
2 4 0.5 0.5
3 10 0.5 0.4
Sample Output
1 0.5000
2 1.1875
3 1.4965
Source
Greater New York 2012
看了解题报告觉得挺简单的啊，自己写，写好了，怎么测试结果都是0，无奈把自己的代码和解题报告比对，对了好久都没发现问题，之后又比对了好多次，最后发现是我把输入向右走的概率输入那里写成了%f，天哪。。。就是这么个小错误，坑了我几个小时了，下次一定要小心再小心，坚决不能再犯这个错误了
题意：给你步数和向左走向右走的概率，剩下的是不走的概率，问你走过的最远距离(这里的意思不是说最后的距离，而是你经过的最远距离，不管是哪一步走的，只要是最远的就可以)的期望值。下面讲解我就copy一下啊
用dp[v][i][j]表示当前前位置在i。途中走到的最右边的位置为j。那么状态转移方程为：
往右走：
1.如果i+1>j。dp[v^1][i+1][i+1]+=dp[v][i][j]*r。
2.如果i+1<=j。dp[v^1][i+1][j]+=dp[v][i][j]*r。
往左走：
dp[v^1][i-1][j]+=dp[v][i][j]*l。
不走：
dp[v^1][i][j]+=dp[v][i][j]*(1-l-r)。
但需要注意的是。i可能为负数所以把起点往右移动n个位置(n为步数)。
#include<stdio.h>
#include<string.h>
double dp[2][205][105];
int main()
{
int i,j,k,n,t,no,c;
double x,y,z,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%lf%lf",&no,&n,&x,&y);
c=0;
z=1.0-x-y;
memset(dp[0],0,sizeof(dp[0]));
dp[0][n][0]=1;
for(k=0;k<n;k++)
{
memset(dp[c^1],0,sizeof(dp[c^1]));
for(i=0;i<=n+n;i++)
{
for(j=0;j<=n;j++)
{
if(dp[c][i][j]>0)
{
if(i+1>j+n)
dp[c^1][i+1][i+1-n]+=dp[c][i][j]*y;
else
dp[c^1][i+1][j]+=dp[c][i][j]*y;
dp[c^1][i-1][j]+=dp[c][i][j]*x;
dp[c^1][i][j]+=dp[c][i][j]*z;
}
}
}
c=c^1;
}
for(i=0,ans=0;i<=n+n;i++)
for(j=1;j<=n;j++)
{
if(dp[c][i][j]>0)
ans+=dp[c][i][j]*j;
}
printf("%d %.4lf\n",no,ans);
}
return 0;
}
#include<stdio.h>
#include<string.h>
double dp[2][205][105];
int main()
{
int i,j,k,n,t,no,c;
double x,y,z,ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%lf%lf",&no,&n,&x,&y);
c=0;
z=1.0-x-y;
memset(dp[0],0,sizeof(dp[0]));
dp[0][n][0]=1;
for(k=0;k<n;k++)
{
memset(dp[c^1],0,sizeof(dp[c^1]));
for(i=0;i<=n+n;i++)
{
for(j=0;j<=n;j++)
{
if(dp[c][i][j]>0)
{
if(i+1>j+n)
dp[c^1][i+1][i+1-n]+=dp[c][i][j]*y;
else
dp[c^1][i+1][j]+=dp[c][i][j]*y;
dp[c^1][i-1][j]+=dp[c][i][j]*x;
dp[c^1][i][j]+=dp[c][i][j]*z;
}
}
}
c=c^1;
}
for(i=0,ans=0;i<=n+n;i++)
for(j=1;j<=n;j++)
{
if(dp[c][i][j]>0)
ans+=dp[c][i][j]*j;
}
printf("%d %.4lf\n",no,ans);
}
return 0;
}
补充：软件开发 , C++ ,
