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;

}

巴特西

cf24D. Broken robot(高斯消元)

题意

Sol

最新文章

热门文章