LOOPS HDU - 3853 (概率dp):(希望通过该文章梳理自己的式子推导)

题意:就是让你从(1,1)走到(r, c)而且每走一格要花2的能量,有三种走法:1,停住。2,向下走一格。3,向右走一格。问在一个网格中所花的期望值。

首先:先把推导动态规划的基本步骤给出来。

·  1.设变量:(注意:设置变量时,要能够使整个求解过程可以分为多个阶段。)

   2.分析阶段决策,并写出决策函数。(也就是能体现前阶段决策后阶段关系的函数)

   3.写出指标函数。(也是就是我们得出解的函数。)

先第一步:设置变量,我们分析这个题的是从(1,1)到(r, c)那么什么能体现“阶段”这个词的东西呢?

     十分明显,那就是步数(把停下也看做一步)啊;那么来具体分析一下。假设:我们走到(x,y)那么他的上一阶段是不是有三种可能,那么这三种上一阶,是不是由上上一阶的决策所决定的。是不是这样就把分层分阶段给划出来了。那么我们就设dp[i][j]  表示走到(x,y)时的期望值,最重要的是i,j的意义。

然后第二步:(分析决策函数)

设Sk便是第k阶段. 设决策为Pk

则S1={(1,1),(2,1),(1,2);则,那么Pk就在S1中决策,我们这道题的决策P1=P01+P02+P0<=>dp[1][1]=dp[1][1]+dp[2][1]+dp[1][2](我只是想更好的让大家理解这个决策)。好了,这个决策函数就写好了

最后第三步:(分析指标函数)

设Vk为指标函数。当然,一般有最值等等类型。我还是回到原题。假设走到(x, y)那么这前部的期望值是由决策函数来决策的。

回到决策函数:Pk=P(k-1)1+P(k-1)2+P(k-1)3  (设h1,h2, h3分别是对应的概率) 那么Vk=(h1*P(k-1)1+h2*P(k-1)2+h3*P(k-1)3+2)

好了,其实指标函数就是动态规划方程式了, dp[i][j]=(p[i][j][0]*dp[i][j]+p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j]+2)  ===>

  dp[i][j]=(p[i][j][1]*dp[i][j+1]+p[i][j][2]*dp[i+1][j]+2)/(1-p[i][j][0]);

ac代码:

#include<cstring>
#include<cstdio>
#define maxn int(1e3+2) double dp[maxn][maxn], p[maxn][maxn][]; int main(){
int r, c;
while (scanf("%d%d", &r, &c) != EOF){
for (int i = ; i <= r;++i)
for (int j = ; j <= c;++j)
for (int k = ; k < ; ++k)
scanf("%lf", &p[i][j][k]);
dp[r][c] = ;
for (int i = r; i>; --i)
for (int j = c; j > ;--j)
if (p[i][j][] == ||i==r&&j==c)continue;
else {
dp[i][j] = (p[i][j][] * dp[i][j + ] + p[i][j][] * dp[i + ][j] + ) / ( - p[i][j][]);
}
printf("%.3lf\n", dp[][]);
}
}
上一篇:HDU 3853 LOOPS 期望dp


下一篇:STL源码剖析(heap)