SPOJ:Robot(数学期望)
There is a robot on the 2D plane. Robot initially standing on the position (0, 0). Robot can make a 4 different moves:
- Up (from (x, y) to (x, y + 1)) with probability U.
- Right (from (x, y) to (x + 1, y)) with probability R.
- Down (from (x, y) to (x, y - 1)) with probability D.
- Left (from (x, y) to (x - 1, y)) with probability L.
After moving N times Robot gets points.
- Let x1 be the smallest coordinate in X-axis, that Robot reached in some moment.
- Let x2 be the largest coordinate in X-axis, that Robot reached in some moment.
- Let y1 be the smallest coordinate in Y-axis, that Robot reached in some moment.
- Let y2 be the largest coordinate in Y-axis, that Robot reached in some moment.
Points achieved by Robot equals to x2 - x1 + y2 - y1.
Given N, U, R, D, L. Calculate expected value of points that Robot achieved after N moves.
Input
First line: One interger N (1 ≤ N ≤ 200).
Second line: Four real numbers U, R, D, L (U + R + D + L = 1, 0 ≤ U, R, D, L ≤ 1) with maximum of 6 numbers after dot.
Output
One number: expected value of points achieved by Robot. The answer will be considered correct if its relative or absolute error does not exceed 10-6.
Example 1
Input:
2
0.100000 0.200000 0.300000 0.400000
Output:
1.780000
Example 2
Input:
3
0.25 0.25 0.25 0.25
Output:
2.375000
题意:二维平面上一个机器人,给出机器人走的步数,已知走上下左右的概率;机器人走到最右边是Xmax,最左边是Xmin,上下同理。问机器人Xmax-Xmin+Ymax-Ymin的期望。
思路:万万没想到,4个方向是分开求,开始一直在想怎么整体求。。。。分开求的话就不难想了,分别求出X方向的最大最小,Y方向的最大最小,搜索一下。。。自己看代码。。。但是注意搜索会超时,注意记忆化。。。
(总之,是个不错的题!
#include<bits/stdc++.h>
using namespace std;
double u,d,l,r,ans;
double dp1[][][],dp2[][][],dp3[][][],dp4[][][];
int vis1[][][],vis2[][][],vis3[][][],vis4[][][];
double maxx(int x,int R,int step)
{
if(vis1[x][R][step]) return dp1[x][R][step];
if(step==) return R;
double res=;
res+=maxx(x,R,step-)*(u+d);
res+=maxx(x+,max(R,x+),step-)*r;
res+=maxx(x-,R,step-)*l;
vis1[x][R][step]=; dp1[x][R][step]=res;
return res;
}
double minx(int x,int L,int step)
{
if(vis2[x][L][step]) return dp2[x][L][step];
if(step==) return L;
double res=;
res+=minx(x,L,step-)*(u+d);
res+=minx(x+,L,step-)*r;
res+=minx(x-,min(L,x-),step-)*l;
vis2[x][L][step]=; dp2[x][L][step]=res;
return res;
}
double maxy(int y,int U,int step)
{
if(vis3[y][U][step]) return dp3[y][U][step];
if(step==) return U;
double res=;
res+=maxy(y,U,step-)*(l+r);
res+=maxy(y+,max(U,y+),step-)*u;
res+=maxy(y-,U,step-)*d;
vis3[y][U][step]=; dp3[y][U][step]=res;
return res;
}
double miny(int y,int D,int step)
{
if(vis4[y][D][step]) return dp4[y][D][step];
if(step==) return D;
double res=;
res+=miny(y,D,step-)*(l+r);
res+=miny(y+,D,step-)*u;
res+=miny(y-,min(D,y-),step-)*d;
vis4[y][D][step]=; dp4[y][D][step]=res;
return res;
}
int main()
{
int N;
cin>>N>>u>>r>>d>>l;
ans+=maxx(,,N);
ans-=minx(,,N);
ans+=maxy(,,N);
ans-=miny(,,N);
printf("%.7lf\n",ans);
return ;
}
最新文章
- H5坦克大战之【画出坦克】
- jQuery Ajax传值给Servlet,在Servlet里Get接受参数乱码的解决方法
- WPF 实现带标题的TextBox
- paip.输入法编程--英文ati化By音标原理与中文atiEn处理流程 python 代码为例
- Cheat (tldr, bropages) - Unix命令用法备忘单
- DB2 递归查询
- (转)Eclipse 下找不到或无法加载主类的解决办法
- 微信小程序-开发入门
- 如何使用mysql命令行
- GitHub学习笔记:本地操作
- Camera测试之Color &; Lens shading Test
- 通过decorators = [,] 的形式给类中的所有方法添加装饰器
- Docker容器常用命令
- mysql 查询优化 ~explain解读之extra解读
- objective-c启用ARC时的内存管理 (循环引用)
- 重复打印相同内容(Doc档)的时候自动生成打印编号
- jmeter-场景-上传文件-send-a-file
- 【C语言】练习2-1
- 12月21日 简单理解Active Recore Callback, destroy_all和delete_all的区别。豆知识(alias),语言学习法(4核心)
- hdu 1799 循环多少次?
热门文章
- spring boot -- 无法读取html文件,碰到的坑
- 小窥React360——用React创建360全景VR体验
- noip2013华容道
- Liunx 下Redis 的安装
- 10.Java web&mdash;JavaBean
- “ORA-01747: user.table.column, table.column 或列说明无效” 的解决方案
- connectTimeOut和readTimeout
- http转成https
- BUPT复试专题—找最小数(2010)
- Error: cannot call methods on draggable prior to initialization; attempted to call