HDU 4418 Time travel——高斯消元+概率dp

HDU 4418 Time travel——高斯消元+概率dp

题意：

给出一个数轴，有一个起点和一个终点，某个人可以走1，2，3……m步，每一种情况有一个概率，初始有一个方向，走到头则返回，问到达终点的期望步数为多少。

思路：

裸的高斯消元+概率dp

#include #include #include #include #include #include using namespace std;const int maxn = 500;const double eps = 1e-4;int T, n, m, y, x, d;double p[maxn], sum;int tot, idx[maxn];bool vis[maxn];double a[maxn][maxn], b[maxn];void Gauss(int num) { int i, j, k, col, max_r; for (k = 0, col = 0; k < num && col < num; k++, col++) { max_r = k; for (i = k+1; i < num; i++) { if (fabs(a[i][col]) > fabs(a[max_r][col])) max_r = i; } if (k != max_r) { for (j = col; j < num; j++) { swap(a[k][j], a[max_r][j]); } swap(b[k], b[max_r]); } b[k] /= a[k][col]; for (j = col+1; j < num; j++) a[k][j] /= a[k][col]; a[k][col] = 1; for (i = 0; i < num; i++) { if (i != k) { b[i] -= b[k] * a[i][k]; for (j = col + 1; j < num; j++) a[i][j] -= a[k][j] * a[i][col]; a[i][col] = 0; } } }}bool bfs() { bool flag = false; tot = 0; memset(idx, -1, sizeof(idx)); memset(vis, false, sizeof(vis)); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); queue q; q.push(x); idx[x] = tot++; while (!q.empty()) { int u = q.front(); q.pop(); if (u == y || u == n-y) { flag = true; a[idx[u]][idx[u]] = 1, b[idx[u]] = 0; continue; } if (vis[u]) continue; vis[u] = true; a[idx[u]][idx[u]] = 1, b[idx[u]] = sum; for (int i = 1; i <= m; i++) { if (fabs(p[i]) < eps) continue; int v = (u+i)%n; if (idx[v] == -1) idx[v] = tot++; a[idx[u]][idx[v]] -= p[i]; q.push(v); } } return flag;}int main() { scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d%d%d%d%d", &n,&m,&y,&x,&d); sum = 0; for (int i = 1; i <= m; i++) { scanf("%lf", &p[i]); p[i] /= 100.0; sum += p[i] * i; } if (d == -1) { printf("%.2f\n", 0.0); continue; } n = 2 * (n-1); x = (d == 0 ? x : n - x); if (!bfs()) printf("Impossible !\n"); else { Gauss(tot); printf("%.2f\n", b[idx[x]]); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。