CF24D Broken robot

传送门

思路

一道典型的高斯消元的期望DP

通过朴素的思考，我们可以获得如下的转移方程

\[f_{i,j}=p_{i,j-1}\times(f_{i,j-1}+1)+p_{i,j}\times(f_{i,j}+1)+p_{i,j+1}\times(f_{i,j+1}+1)+p_{i+1,j}\times(f_{i+1,j}+1) \]

（我们这里采用的是老套路逆推，而要注意到在边界的点移动的概率可能不为 \(\frac1 4\)）

乍一看，则不就是简简单单的高消嘛

然后看一下数据范围，好家伙 \(O((nm)^3)\) 怎么可能能过

但再仔细看，每个方程最多只有三个系数不为 \(0\)

而且第 \(i\) 行的转移和第 \(i-1\) 行没有关系，那我们就考虑分开每行高消！

这样我们每次其实就是做一个带状矩阵的高斯消元

时间复杂度为 \(O(mn)\)

代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
inline int reads()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, x, y;
double f[1005];
double a[1005][1005];
inline void Gauss()
{
    for(int i = 1; i <= m; i++)
    {
        double mul = a[i + 1][i] / a[i][i];
        for(int j = i; j < i + 2; j++)
            a[i + 1][j] -= mul * a[i][j];
        a[i + 1][m + 1] -= mul * a[i][m + 1];
    }
    for(int i = m; i >= 1; i--)
    {
        f[i] = a[i][m + 1];
        f[i] -= a[i][i + 1] * f[i + 1];
        f[i] /= a[i][i];
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = reads(), m = reads(), x = reads(), y = reads();
    if(m == 1)
    {
        printf("%d", (n - x) << 1);
        return 0;
    }
    n -= x;
    while(n--)
    {
        for(int i = 1; i <= m; i++)
        {
            if(i == 1)
                a[i][i - 1] = 0, a[i][i] = 2.0 / 3.0, a[i][i + 1] = -1.0 / 3.0, a[i][m + 1] = f[i] / 3.0 + 1.0;
            else if(i == m)
                a[i][i - 1] = -1.0 / 3.0, a[i][i] = 2.0 / 3.0, a[i][i + 1] = 0, a[i][m + 1] = f[i] / 3.0 + 1.0;
            else
                a[i][i - 1] = -0.25, a[i][i] = 0.75, a[i][i + 1] = -0.25, a[i][m + 1] = f[i] * 0.25 + 1.0;
        }
        Gauss();
    }
    printf("%.4lf", f[y]);
    return 0;
}
luogu题解高斯消元期望DP

相关

P1850 换教室 期望dp

高斯消元法（正在更）

[算法] 高斯消元法（Python）

【模板】高斯消元法

高斯消元与线性空间

【题解】金牌导航-高斯消元/Luogu P3232 游走

【学习笔记】高斯消元

高斯消元

标签