问题描述:

在$N*M$的网格中有一个起始位置为$(x, y)$的robot。它每一步会随机的执行四个操作中一个:待在原地,向左,向右,向下(它是不能够移动到网格之外的)。然后问你它移动到第$N$行的步数期望值为多少。

输入:

第一行两个整数$N,M$,表示$N*M$的网格($1<=n, m<=1000$)
第二行两个整数$x,y$,表示起始位置为$(x, y)$

输出:

输出到第$n$行的期望步数

思路:

这道题中的状态转移方程并不难想到。但是我们发现这些状态会相互影响,并且无法推出其中的任何一个。对于这种期望DP就要用到另一种套路“高斯消元”。

按照套路我们依然从后往前推,第$n$行的所有期望值都为0,我们把这个作为初值向前DP。对于每一行我们都能根据转移方程列出一个方程组,而且我们发现其中的每个方程只有2-3个变量(边界时为两个,其余为3个)。于是我们可以不用普通$O(N^3)$的高斯消元,而是可以YY出一个类似的$O(n)$的消元方法,然后对于每一行都进行一遍这个操作,总复杂度为$O(nm)$。

代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <string>
#define MAXN 1005
using namespace std;

int n, m, x, y;
double a[MAXN][5], g[MAXN], f[MAXN], w[MAXN];

void guass()
{
    for(int i=1; i<m; i++)
    {
        double rate=a[i+1][0]/a[i][1];
        a[i+1][0]-=a[i][1]*rate;
        a[i+1][1]-=a[i][2]*rate;
        w[i+1]-=w[i]*rate;
    }
    f[m]=w[m]/a[m][1];
    for(int i=m-1; i>=1; i--) f[i]=(w[i]-a[i][2]*f[i+1])/a[i][1];
}

int main()
{
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i=1; i<=m; i++)
    {
        g[i]=2;
        if(i>1) g[i]++;
        if(i<m) g[i]++;
        g[i]=1.0/g[i];
    }
    for(int i=n-1; i>=x; i--)
    {
        for(int j=1; j<=m; j++)
        {
            if(j!=1) a[j][0]=-g[j];
            a[j][1]=1-g[j];
            if(j!=m) a[j][2]=-g[j];
            w[j]=g[j]*f[j]+1;
        }
        guass();
    }
    printf("%lf\n", f[y]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注