c/c++语言开发共享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("%dn", 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 %dn", 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("%dn", 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("%.2lfn", g[x][x]); } int main() {     //freopen("a.in", "r", stdin);     //freopen("b.out", "w", stdout);     for(int t = read(); t; t--, solve());     return 0; }