2019-02-12

有后效性的状态转移方程

dp学习

cf 24D

题目链接

题意

有一个n*m的棋盘，机器人初始的位置在(i, j), 机器人可以向左，或者向右，或者向下移动，问移动到最后一行的走的步数的期望。

题解

设$F(i, j)$表示第i行第j列的期望。

若$j=1或者j=m$时，状态转移方程为：

$F(i, j) = \frac{F(i+1, j)+F(i, j-1)+F(i, j+1)}{3}+1$

j为其他值的时候

$F(i, j) = \frac{F(i, j)+F(i+1, j)+F(i, j-1)+F(i, j+1)}{4}+1$

初始化的值为$F(n, j) = 0, 1\le j\le m$

然后从下向上不断的递推。

这种逆向递推的思想很重要。

ac code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
double dp[maxn][maxn];
int deg[maxn];
int n, m;
int main()
{
    ios::sync_with_stdio(false);
    int p, q;
    scanf("%d%d%d%d", &n, &m, &p, &q);
    int x;
    for(int i=1;i<=m;++i){
		x= 2; if(i>1)++x;if(i<m)++x;
		deg[i]=x;
	}
    for(int row=n-1; row>=p; row--){
        for(int d=1; d<=45; d++){
            for(int col = 1; col<=m; col++){
                dp[row][col] = (dp[row][col]+dp[row+1][col]+dp[row][col+1]+dp[row][col-1])/deg[col]+1;
            }
        }
    }
    printf("%0.6f\n",dp[p][q]);
    return 0;
}

未解决的问题

本文标题:有后效性的状态转移方程

文章作者:Babydragon

发布时间:2019-02-12, 23:20:49

最后更新:2019-02-12, 23:46:40

原始链接:http://baolintian.github.io/2019/02/12/有后效性的状态转移方程/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。