加载中…HDU 3853 LOOPS 北邮邀请赛
(2011-07-18 19:25:07)
标签：
hdu3853loops北邮邀请赛it |
分类： 动态规划 |
题目描述：
给你R*C的地图，对于每个点，有a的概率不动，b的概率往右走一格，c的概率往下走一格。
为你从0，0走到r-1，c-1需要的期望步数。
解题报告：
dp[i][j]表示从i，j走到r-1，c-1的期望。由于ij能走到ij，i j+1和i+1 j
所以dp[i][j] = a * (2 + dp[i][j]) + b * (2 + dp[i][j + 1] + c * (2 + dp[i + 1][j])
把右边的dp[i][j]移到左边，就可以得到dp[i][j]的转移。比较容易理解。
代码如下：
if (a
== n - 1 && b == m - 1) return
0.0;
if(x[a][b][0] == 1.0)
return 0;
if
(dp[a][b] < 0)
{
dp[a][b] = (2 * (x[a][b][0] +
x[a][b][1] + x[a][b][2]));
if (b + 1 < m)
dp[a][b] += x[a][b][1] * jeo(a, b + 1);
if (a + 1 < n)
dp[a][b] += x[a][b][2] * jeo(a + 1, b);
dp[a][b] /= (1 -
x[a][b][0]);
}
return
dp[a][b];
while(scanf("%d%d", &n,
&m) != EOF)
{
for(int i = 0; i
< n; i++)
for(int j = 0; j < m; j++)
for(int k =
0; k < 3; k++)
scanf("%lf",
&x[i][j][k]);
for(int i = 0; i
< n; i++)
for(int j = 0; j < m; j++)
dp[i][j] = -1;
printf("%.3f\n", jeo(0,
0));
}
return
0;
给你R*C的地图，对于每个点，有a的概率不动，b的概率往右走一格，c的概率往下走一格。
为你从0，0走到r-1，c-1需要的期望步数。
解题报告：
dp[i][j]表示从i，j走到r-1，c-1的期望。由于ij能走到ij，i j+1和i+1 j
所以dp[i][j] = a * (2 + dp[i][j]) + b * (2 + dp[i][j + 1] + c * (2 + dp[i + 1][j])
把右边的dp[i][j]移到左边，就可以得到dp[i][j]的转移。比较容易理解。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, m;
double x[1002][1002][3];
double dp[1002][1002];
double jeo(int a, int b)
{
}
int main()
{
}
喜欢
0
赠金笔