时间限制: 10 Sec 内存限制: 128 MB
题目描述
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.
输入
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 ≤ 1000). 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.
输出
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.
样例输入
4
1 1 0.5 0.5
2 4 0.5 0.5
3 10 0.5 0.4
4 1000 0.5 0.4
样例输出
1 0.5000
2 1.1875
3 1.4965
4 3.9995
O(n^3)概率dp，被卡掉了，但其他oj应该能过去，自家oj应该是加了一组15*1000的数据
//O(n^3)
#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1010;
int n,s;
double l,r,inp;
double dp[3][maxn<<1][maxn<<1];
int main()
{
int _;
scanf("%d",&_);
while(_--){
scanf("%d%d%lf%lf",&n,&s,&l,&r);
inp=1.0-l-r;
memset(dp,0,sizeof(dp));
dp[0][1000][1000]=1;
int f=0;
for(int i=1;i<=s;i++,f^=1)
for(int j=1000-i;j<=1000+i;j++){
for(int k=j>1000?j:1000;k<=1000+i;++k){
if(j==k)
dp[f^1][j][k]=dp[f][j][k]*inp+dp[f][j-1][k-1]*r+dp[f][j-1][k]*r;
else
dp[f^1][j][k]=dp[f][j][k]*inp+dp[f][j-1][k]*r+dp[f][j+1][k]*l;
}
}
double ans=0;
for(int i=1000-s;i<=1000+s;++i)
for(int j=1000;j<=1000+s;++j)
ans+=dp[f][i][j]*(j-1000);
printf("%d %.4f\n",n,ans);
}
return 0;
}
//O(n^2)
#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1010;
double l,r,inp;
double dp[maxn][maxn];
double solve(int n){
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++){
dp[i][j]=0;
if(j) dp[i][j]+=dp[i-1][j-1]*r;
if(j<i) dp[i][j]+=dp[i-1][j]*inp;
else dp[i][j]+=inp;
if(j<i-1) dp[i][j]+=dp[i-1][j+1]*l;
else dp[i][j]+=l;
}
}
double ans=0;
for(int i=1;i<=n;i++) ans+=(dp[n][i]-dp[n][i-1])*i;
return ans;
}
int main()
{
int _;
scanf("%d",&_);
while(_--){
int n,num;
scanf("%d %d %lf %lf",&num,&n,&l,&r);
inp=1-l-r;
printf("%d %.4lf\n",num,solve(n) );
}
return 0;
}
Moriarty Yang 