CF24D Broken robot

题目描述

你收到的礼物是一个非常聪明的机器人,行走在一块长方形的木板上。不幸的是,你知道它是坏的,表现得相当奇怪(随机)。该板由n行和m列的单元格组成。机器人最初是在i行和j j列的某个单元格上。然后在每一步机器人可以到另一个单元。目的是去底层(n次)行。机器人可以停留在当前单元,向左移动,向右边移动,或者移动到当前下方的单元。如果机器人在最左边的列不能向左移动,如果它是在最右边的列不能向右移动。在每一步中,所有可能的动作都是同样可能的。返回步的预期数量达到下面的行。

输入格式

在第一行,您将得到两个空间分隔的整数n和 $ N $ and $ M $ ( $ 1\le N,M\le 1000 $ ).。在第二行,您将得到另外两个空间分隔的整数i i和j ( $ 1\le i\le N,1\le j\le M $ ) ),即初始行的数目和初始列的数目。注意,(1,1)(1,1)是棋盘的左上角,(n,m)(n,m)是右下角。

输出格式

在小数点后至少有4个4位数的线上输出预期的步骤数。

样例输入

10 14
5 14

样例输出

18.0038068653

分析

期望dp,方程:

$$f(i,j)=\frac{1}{4}[f(i,j)+f(i,j-1)+f(i,j+1)+f(i+1,j)]$$

棋盘边缘只有三个方向,就改成$\frac{1}{3}$。

转移有环,自然采用高斯消元。

本来想整个棋盘一起消,一看$1000^2$就有$10^6$个元,还是$O(n^3)$算法,不可取。

不过发现下面的行dp值与上面的行无关,所以我们可以从下往上一行一行做,把下一行的dp值看作常数代入。

然后算一下复杂度:$1000^3$,好像会爆,不敢写……

结果看完题解发现每行实际上只有3个数非零,所以每行只要消掉2个元,而且每行只要消掉下一行即可,复杂度$O(n)$。

所以高斯消元的复杂度要具体情况具体分析,观察非0数的分布,不要被裸高斯消元$O(n^3)$的复杂度吓到。

(又想起省选也是一道每行两个数非0的高斯消元,当时还用$O(n^3)$结果T了……)

代码

#include <bits/stdc++.h>

const int N = 1050;

double a[N][4];

void gauss(int n, double res[N]) {
    for (int i = 1; i < n; i++) {
        double k = a[i+1][0] / a[i][1];
        a[i+1][0] = 0;
        a[i+1][1] -= a[i][2] * k;
        a[i+1][3] -= a[i][3] * k;
    }
    res[n] = a[n][3] / a[n][1];
    for (int i = n-1; i >= 1; i--)
        res[i] = (a[i][3] - a[i][2] * res[i+1]) / a[i][1];
}

int main() {
    int n, m, sx, sy;
    double f[N] = {0};
    scanf("%d%d%d%d", &n, &m, &sx, &sy);
    for (int i = n-1; i >= sx; i--) {
        for (int j = 1; j <= m; j++) {
            double p = 4;
            if (j == 1) p -= 1;
            if (j == m) p -= 1;
            p = 1.0 / p;

            if (j != 1) a[j][0] = p;
            a[j][1] = p - 1;
            if (j != m) a[j][2] = p;
            a[j][3] = -p*f[j]-1;
        }
        gauss(m, f);
    }
    printf("%.10lf\n", f[sy]);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论