牛客网笔试题 随机的机器人(概率DP+滚动数组) 不念不忘少年蓝@ 2021-12-04 07:43 171阅读 0赞 ## 题意: ## 有一条无限长的纸带,分割成一系列的格子,最开始所有格子初始是白色。现在在一个格子上放上一个萌萌的机器人(放上的这个格子也会被染红),机器人一旦走到某个格子上,就会把这个格子涂成红色。现在给出一个整数n,机器人现在会在纸带上走n步。每一步,机器人都会向左或者向右走一个格子,两种情况概率相等。机器人做出的所有随机选择都是独立的。现在需要计算出最后纸带上红色格子的期望值。 **输入描述:** 输入包括一个整数n(0 ≤ n ≤ 500),即机器人行走的步数。 **输出描述:** 输出一个实数,表示红色格子的期望个数,保留一位小数。 示例1 ## 输入 ## 4 ## 输出 ## 3.4 ## 分析:开始还以为是个结论或者规律题,看了题解才知道是概率dp,dp\[i\]\[j\]\[k\]表示走了i步,纸带上有j个红色格子,机器人位于第k个红格子的概率,因为i\*j\*k最大为500^3远远大于空间限制,所以第1维采用滚动数组。dp\[0\]\[1\]\[1\]=1.0。转移方程可参考[https://blog.csdn.net/xiaxzhou/article/details/73382283][https_blog.csdn.net_xiaxzhou_article_details_73382283]。 ## ## 代码: ## #include<bits/stdc++.h> using namespace std; const int N = 505; double dp[2][N][N]; int main() { int n; cin>>n; dp[0][1][1]=1.0; int last,now; for(int i=1;i<=n;i++){ last=(i-1)%2; now=i%2; for(int j=1;j<=i+1;j++)for(int k=0;k<=j;k++)dp[now][j][k]=0; for(int j=1;j<=i+1;j++){ for(int k=1;k<=j;k++){ //goto left if(k==1){ dp[now][j+1][k]+=dp[last][j][k]*0.5; } else{ dp[now][j][k-1]+=dp[last][j][k]*0.5; } //goto right if(k==j){ dp[now][j+1][k+1]+=dp[last][j][k]*0.5; } else{ dp[now][j][k+1]+=dp[last][j][k]*0.5; } } } } double ans=0; for(int j=1;j<=n+1;j++) for(int k=0;k<=j+2;k++) ans+=j*dp[now][j][k]; printf("%.1f\n",ans); return 0; } [https_blog.csdn.net_xiaxzhou_article_details_73382283]: https://blog.csdn.net/xiaxzhou/article/details/73382283
还没有评论,来说两句吧...