cf24D. Broken robot(高斯消元)

题意

题目链接

sol

今天上午的a题。想出来怎么做了但是没时间写了qwq

思路很简单，首先把转移方程列一下，发现每一个位置只会从下一行/左右转移过来，而且第n行都是0，那么往下转移的都可以回带。

剩下的也可以联立一下直接解(我在说什么。。)

然后推一推就行了。对于我这种平均每两个符号写错一个的来说可能调起来比较自闭qwq

#include<bits/stdc++.h> 
#define pair pair<double, double>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define ll long long 
//#define double long double 
#define fin(x) {freopen(#x".in","r",stdin);}
#define fout(x) {freopen(#x".out","w",stdout);}
using namespace std;
const int maxn = 3001, mod = 1e9 + 7;
const double eps = 1e-9;
template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;}
template <typename a, typename b> inline ll add(a x, b y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename a, typename b> inline void add2(a &x, b y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename a, typename b> inline ll mul(a x, b y) {return 1ll * x * y % mod;}
template <typename a, typename b> inline void mul2(a &x, b y) {x = (1ll * x * y % mod + mod) % mod;}
template <typename a> inline void debug(a a){cout << a << '\n';}
template <typename a> inline ll sqr(a x){return 1ll * x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, x, y;
double f[maxn][maxn], a[maxn], b[maxn], c[maxn];
signed main() {
    n = read(); m = read(); x = read(), y = read();
    if(m == 1) {cout << 2 * (n - x); return 0;}
    for(int i = n - 1; i >= 1; i--) {
        a[1] = 1; b[1] = -0.5, c[1] = 1.5 + 0.5 * f[i + 1][1];
        for(int j = 2; j <= m - 1; j++) {
            double p = (-0.25 / a[j - 1]);
            a[j] = 0.75 - p * b[j - 1];
            b[j] = -0.25;
            c[j] = 1.0 + 0.25 * f[i + 1][j] - p * c[j - 1];
        }
        double tmp = -0.5 / a[m - 1];
        f[i][m] = (c[m - 1] * tmp - 1.5 - 0.5 * f[i + 1][m]) / (b[m - 1] * tmp - 1);
        f[i][m - 1] = (c[m - 1] - b[m - 1] * f[i][m]) / a[m - 1];
        for(int j = m - 2; j >= 1; j--)
            f[i][j] = (c[j] - b[j] * f[i][j + 1]) / a[j];
    }
    printf("%.5lf", f[x][y]);
    return 0;
}