HDU4418 Time travel(期望dp 高斯消元)

题意

sol

mdzz这题真的太恶心了。。

首先不难看出这就是个高斯消元解方程的板子题

\(f[x] = \sum_{i = 1}^n f[to(x + i)] * p[i] + ave\)

\(ave\)表示每次走的期望路程

然后一件很恶心的事情是可以来回走，而且会出现\(m > n\)的情况(因为这个调了两个小时。。)

一种简单的解决方法是在原序列的后面接一段翻转后的序列

比如\(1 \ 2 \ 3 \ 4\)可以写成\(1 2 3 4 3 2\)

然后列式子解方程就行了

附送一个数据生成器

#include<bits/stdc++.h>
using namespace std;
int main() {
    freopen("a.in", "w", stdout);
    srand((unsigned)time(null));
    int t = 30;
    printf("%d\n", t);
    while(t--) {
        int n = rand() % 100 + 1, m = rand() % 20 + 1, y = rand() % n, x = rand() % n, d = rand() % 2;
        if(x == 0 || x == n - 1) d = -1;
        printf("%d %d %d %d %d\n", n, m, y, x, d);
        int res = 100;
        for(int i = 1; i <= m - 1; i++) {
            int rd;
            if(res == 0) rd = 0;
            else rd = rand() % res + 1;
            printf("%d ", rd); res -= rd;
        }
        printf("%d\n", res);
    }
    return 0;
}

#include<bits/stdc++.h> 
#define ll long long 
using namespace std;
const int maxn = 1001, mod = 998244353;
const double eps = 1e-9;
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, d, lim, vis[maxn];
double g[maxn][maxn], p[maxn], ave;
int gauss() {
    for(int i = 1; i < lim; i++) {
        int mx = i;
        for(int j = i + 1; j < lim; j++) 
            if(fabs(g[j][i]) > fabs(g[mx][i])) mx = j;
        swap(g[i], g[mx]);
        //assert(g[i][i] > eps);
        if(fabs(g[i][i]) < eps) return -1;
        for(int j = i + 1; j < lim; j++) {
            double p = g[j][i] / g[i][i];
            for(int k = i + 1; k <= lim; k++) 
                g[j][k] -= g[i][k] * p;
        }
    }   
    for(int i = 1; i < lim; i++) if(fabs(g[i][i]) < eps) return -1;
    for(int i = lim - 1; i >= 1; i--) {
        g[i][i] = g[i][lim] / g[i][i];
        for(int j = i - 1; j >= 1; j--)
            g[j][lim] -= g[j][i] * g[i][i], g[j][i] = 0;
    }
}
int walk(int a, int b) { 
    b %= (lim - 1);
    int x = a + b;
    if(x <= lim - 1) return x;
    return x % (lim - 1);
}
void init() {
    memset(g, 0, sizeof(g));
    memset(vis, 0, sizeof(vis));
    ave = 0;
}
void bfs() {
    queue<int> q; q.push(x); vis[x] = 1;
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = 1; i <= m; i++) {
            if(p[i] > eps) {
                int t = walk(x, i);
                if(!vis[t]) q.push(t), vis[t] = 1;
            }
        }
    }
}
void solve() {
    init();
    n = read(); m = read(); y = read() + 1; x = read() + 1; d = read();
    lim = (n << 1) - 1;
    for(int i = 1; i <= m; i++) p[i] = (double) read() / 100, ave += (double) i * p[i];
    if(x == y) {puts("0.00"); return;}
    if(d > 0 || (d == -1 && x > y)) x = n - x + 1, y = n - y + 1;
    bfs();
    for(int i = 1; i <= 2 * n - 2; i++) {
        g[i][i] = 1; 
        if(!vis[i]) {g[i][lim] = 3e18; continue;}
        if(i == y || (lim - i + 1 == y)) continue;
        g[i][lim] = ave;
        for(int j = 1, t; j <= m; j++) {
            t = walk(i, j);
            g[i][t] -= p[j];
        }
    }
    if((!vis[y] && !vis[lim - y + 1]) || (gauss() == -1)) puts("impossible !");
    else printf("%.2lf\n", g[x][x]);
}
int main() {
    //freopen("a.in", "r", stdin);
    //freopen("b.out", "w", stdout);
    for(int t = read(); t; t--, solve());
    return 0;
}