题解 CF24D 【Broken robot】

· · 题解

Description

现在有一个机器人，最初站在 n \times m\ (1 \leq n,m\leq 1000) 矩阵中的 (x,y)\ (1 \leq x \leq n, 1\leq y \leq m) 位置。每次它会等概率的选择 原地不动，向左移动，向右移动，向下移动 四种操作。当然，机器人在第 1 列时不会选择向左移动，第 m 列时不会选择向右移动。求机器人到达第 n 行的期望步数，至少精确到 10^{-4} 。

Source

[Luogu]CF24D

[Codeforces]24D

Solution

求期望步数，很容易想到 期望DP 。我们用 f_{i,j} 表示从 (i,j) 走到最后一行的期望步数，那么初始状态就是 f_{n,i} = 0\ (1 \leq i \leq m)（从最后一行走到最后一行的期望步数为 0），要求的答案就是 f_{x,y}（根据状态即能得到），状态转移方程如下（分 3 种情况讨论）：

f_{i,j}=\left\{\begin{matrix} \frac{1}{3}\left ( f_{i,j} + f_{i,j+1} + f_{i+1,j} \right )+1& (j=1)\\ \frac{1}{4}\left ( f_{i,j} + f_{i,j+1} + f_{i,j-1} + f_{i+1,j} \right )+1& (1< j< m) \\ \frac{1}{3}\left ( f_{i,j} + f_{i,j-1} + f_{i+1,j} \right )+1& (j=m) \\ \end{matrix}\right.

值得注意的是：m = 1 时比较特殊，因为不能向左和向右移动，此时

f_{i,j}=\frac{1}{2} \left( f_{i,j} + f_{i+1,j} \right) + 1

这个转移方程是倒推的，并且有后效性，所以不能直接转移。在求 f_{i,j} 时，f_{i+1,j} 是 已知 的，而 f_{i,j-1},f_{i,j},f_{i,j+1} 都是 未知 的，我们把未知量移到左边，把已知量移到右边，可以得到：

\left\{\begin{matrix} -\frac{2}{3}f_{i,j}+\frac{1}{3}f_{i,j+1}=-\frac{1}{3}f_{i+1,j}-1 & (j=1)\\ \frac{1}{4}f_{i,j-1}-\frac{3}{4}f_{i,j}+\frac{1}{4}f_{i,j+1}=-\frac{1}{4}f_{i+1,j}-1& (1 < j < m)\\ \frac{1}{3}f_{i,j-1}-\frac{2}{3}f_{i,j}=-\frac{1}{3}f_{i+1,j}-1 & (j=m)\\ \end{matrix}\right.

同理，m = 1​ 时，

-\frac{1}{2}f_{i,j} = -\frac{1}{2}f_{i+1,j} - 1

我们会发现一共有 m 个未知数和 m 个方程，很容易想到 高斯消元 求解未知量 f_{i,1} \sim f_{i,m}\ (1 \leq i < n) 。

比如说，当 m = 5​ 时，所构成的矩阵就是：

\begin{bmatrix} -\frac{2}{3} & \color{blue}{\frac{1}{3}} & 0 & 0 & 0\\ \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}} & 0 & 0\\ 0 & \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}} & 0\\ 0 & 0 & \color{red}{\frac{1}{4}} & -\frac{3}{4} & \color{blue}{\frac{1}{4}}\\ 0 & 0 & 0 & \color{red}{\frac{1}{3}} & -\frac{2}{3}\\ \end{bmatrix} =\begin{bmatrix} -\frac{1}{3}f_{i+1,j}-1\\ -\frac{1}{4}f_{i+1,j}-1\\ -\frac{1}{4}f_{i+1,j}-1\\ -\frac{1}{4}f_{i+1,j}-1\\ -\frac{1}{3}f_{i+1,j}-1\\ \end{bmatrix}

本来 高斯消元 的时间复杂度应该是 O(n^3) 的。但是观察矩阵能够发现，其实这是一个稀疏矩阵，未知数全部集中在对角线上，0 的地方不需要消元，我们需要消元的只有 m - 1 个数（上图 红色 的数字），回带时原方程中也只需要消去 m - 1 个数（上图 蓝色 的数字），所以本题中 高斯消元 时间复杂度为 O(m) 。总时间复杂度为 O(nm) 。

Code

#include <bits/stdc++.h>
using namespace std;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    x = f ? -x : x;
}

const int MAXN = 1000;
int n, m, x, y;
double a[MAXN + 5][MAXN + 5], f[MAXN + 5][MAXN + 5];

inline void Gauss() {
    for (int i = 1; i < m; ++i) {
        double t = a[i][i];
        a[i][i] = 1;
        a[i][i + 1] /= t;
        a[i][m + 1] /= t;
        t = a[i + 1][i];
        a[i + 1][i] = 0;
        a[i + 1][i + 1] -= t * a[i][i + 1];
        a[i + 1][m + 1] -= t * a[i][m + 1];
    }//消元，消去下一行方程开头的未知数 
    a[m][m + 1] /= a[m][m];
    a[m][m] = 1;//求出最后一个未知数的解 
    for (int i = m - 1; i; --i)
        a[i][m + 1] -= a[i + 1][m + 1] * a[i][i + 1];//回带，消去下一行方程末尾的未知数
}

int main() {
    freopen("eat.in", "r", stdin);
    freopen("eat.out", "w", stdout);
    read(n), read(m), read(x), read(y);
    for (int i = n - 1; i >= x; --i) {
        if (m == 1) {
            a[1][1] = -1.0 / 2;
            a[1][m + 1] = -f[i + 1][1] / 2.0 - 1;//特判 m = 1 
        } else {
            a[1][1] = -2.0 / 3;
            a[1][2] = 1.0 / 3;
            a[1][m + 1] = -f[i + 1][1] / 3.0 - 1.0;
            for (int j = 2; j < m; ++j) {
                a[j][j] = -3.0 / 4;
                a[j][j - 1] = a[j][j + 1] = 1.0 / 4;
                a[j][m + 1] = -f[i + 1][j] / 4.0 - 1;
            }
            a[m][m] = -2.0 / 3;
            a[m][m - 1] = 1.0 / 3;
            a[m][m + 1] = -f[i + 1][m] / 3.0 - 1;
        }//构造矩阵 
        Gauss();//高斯消元 
        for (int j = 1; j <= m; ++j) f[i][j] = a[j][m + 1];//赋值求出的解 
    }
    printf("%.10lf\n", f[x][y]);
    return 0;
}