HDU3853

Akemi Homura is a Mahou Shoujo (Puella Magi/Magical Girl). Homura wants to help her friend Madoka save the world. But because of the plot of the Boss Incubator, she is trapped in a labyrinth called LOOPS.

The planform of the LOOPS is a rectangle of R*C grids. There is a portal in each grid except the exit grid. It costs Homura 2 magic power to use a portal once. The portal in a grid G(r, c) will send Homura to the grid below G (grid(r+1, c)), the grid on the right of G (grid(r, c+1)), or even G itself at respective probability (How evil the Boss Incubator is)! At the beginning Homura is in the top left corner of the LOOPS ((1, 1)), and the exit of the labyrinth is in the bottom right corner ((R, C)). Given the probability of transmissions of each portal, your task is help poor Homura calculate the EXPECT magic power she need to escape from the LOOPS.

裸的期望DP

dp[i[j]表示当前在i,j位置,到达终点的期望

我们不难看出转移方程为

dp[i][j]=dp[i][j]*p0+dp[i][j+1]*p1+dp[i+1][j]*p2

解这个式子有两种方法

1.高斯消元

2.把右边的dp[i][j]除到左边

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cmath>
 6 using namespace std;
 7 const int MAXN=2001;
 8 const int INF=0x7fffff;
 9 double dp[MAXN][MAXN];//走到i,j的期望 
10 struct node
11 {
12     double a,b,c;
13     void clear(){a=b=c=0.0;}
14 }map[MAXN][MAXN];
15 int n,m;
16 const double eps=1e-5;
17 int main()
18 {
19     dp[n][m]=0;
20     while(scanf("%d%d",&n,&m)!=EOF)
21     {
22         memset(dp,0.00,sizeof(dp));
23         dp[n][m]=0;
24         for(int i=1;i<=n;i++)
25             for(int j=1;j<=m;j++)
26                 map[i][j].clear();
27         for(int i=1;i<=n;i++)
28             for(int j=1;j<=m;j++)
29                 scanf("%lf%lf%lf",&map[i][j].a,&map[i][j].b,&map[i][j].c);
30         for(int i=n;i>=1;i--)
31             for(int j=m;j>=1;j--)
32             {
33                 if(i==n&&j==m)    continue;
34                 if(fabs(1.00-map[i][j].a)<eps)    continue;
35                 dp[i][j]=(map[i][j].b*dp[i][j+1]+map[i][j].c*dp[i+1][j]+2.00)/(1.0-map[i][j].a);
36             }    
37         printf("%.3lf\n",dp[1][1]);
38     }
39     
40     
41     return 0;
42 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI启蒙研究院

从一个双控开关思考神经网络(上)

962
来自专栏Fish

TensorFlow编程入门(二)

Classification 这里使用深度学习经典数据MNIST手写字符集。Classification主要就是给输入的字符集分出[0-9]十个类。它的输入图片...

1947
来自专栏图形学与OpenGL

实验6 Bezier曲线生成

了解曲线的生成原理,掌握几种常见的曲线生成算法,利用VC+OpenGL实现Bezier曲线生成算法。

941
来自专栏贾志刚-OpenCV学堂

OpenCV中图像算术操作与逻辑操作

在图像处理中有两类最重要的基础操作分别是图像点操作与块操作,简单点说图像点操作就是图像每个像素点的相关逻辑与几何运算、块操作最常见就是基于卷积算子的各种操作、实...

45210
来自专栏数据结构与算法

牛客NOIP提高组(三)题解

考虑算一个位置的概率,若想要$k$步把它干掉,那么与他距离为$1$到$k - 1$的点都必须阻塞

1393
来自专栏人工智能LeadAI

TensorFlow中的Nan值的陷阱

之前在TensorFlow中实现不同的神经网络,作为新手,发现经常会出现计算的loss中,出现Nan值的情况,总的来说,TensorFlow中出现Nan值的情况...

5945
来自专栏CreateAMind

代码开放--模仿学习3篇论文及官方效果视频

https://sites.google.com/view/one-shot-imitation

1092
来自专栏用户2442861的专栏

基于级联分类器的多目标检测

原文地址:http://blog.csdn.NET/ariesjzj/article/details/8639208

2941
来自专栏小鹏的专栏

tf28: 手写汉字识别

MNIST手写数字数据集通常做为深度学习的练习数据集,这个数据集恐怕早已经被大家玩坏了。本帖就介绍一个和MNIST类似,同时又适合国人练习的数据集-手写汉字数...

8339
来自专栏QQ音乐前端团队专栏

前端图片主题色提取

对于需要根据用户“定制”、“生成”的图片,这样的方式就有了一个上传图片---->后端计算---->返回结果的时间,等待时间也许就比较长了。由此,我尝试着利用 c...

1.6K15

扫码关注云+社区

领取腾讯云代金券