【高斯消元 求期望】HDU 4418 Time travel
KIDx的解题报告题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4418
题意：一个人在数轴上来回走，以pi的概率走i步i∈，给定n（数轴长度），m，e（终点），s（起点），d（方向），求从s走到e经过的点数期望
解析：设E是人从x走到e经过点数的期望值，显然对于终点有：E = 0
一般的：E = sum((E+i) * p)(i∈)
(走i步经过i个点，所以是E+i)
建立模型：高斯消元每个变量都是一个互不相同的独立的状态，由于人站在一个点，还有一个状态是方向！例如人站在x点，有两种状态向前、向后，不能都当成一种状态建立方程，所以要把两个方向化为一个方向从而使状态不受方向的影响
实现：
n个点翻过去（除了头尾两个点~~~）变为2*(n-1)个点，例如：
6个点：012345 ---> 0123454321
那么显然，从5开始向右走其实就是相当于往回走
然后方向就由两个状态转化成一个状态的，然后每个点就是只有一种状态了，对每个点建立方程高斯消元即可
bfs判断是否可以到达终点，顺便建立方程
#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#include <queue>#include <algorithm>#include <math.h>using namespace std;#define M 205#define eps 1e-8int equ, var;double a, x;int Gauss (){int i, j, k, col, max_r;for (k = 0, col = 0; k < equ && col < var; k++, col++){max_r = k;for (i = k+1; i < equ; i++)if (fabs (a) > fabs (a))max_r = i;if (k != max_r){for (j = col; j < var; j++)swap (a, a);swap (x, x);}x /= a;for (j = col+1; j < var; j++) a /= a;a = 1;for (i = 0; i < equ; i++) if (i != k){x -= x * a;for (j = col+1; j < var; j++) a -= a * a;a = 0;}}return 1;}//has表示人在x点时的变量号，因为我们只用可达状态建立方程，所以需要编号int has, vis, k, e, n, m;double p, sum;int bfs (int u){memset (has, -1, sizeof(has));memset (a, 0, sizeof(a));//忘记初始化WA勒，以后得注意memset (vis, 0, sizeof(vis));int v, i, flg = 0;queue<int> q;q.push (u);k = 0;has = k++;while (!q.empty ()){u = q.front ();q.pop ();if (vis) continue;vis = 1;if (u == e || u == n-e)//终点有两个，你懂的~{a]] = 1;x] = 0;flg = 1;continue;}//E = sum ((E+i) * p)// ----> E - sum(p*E) = sum(i*p)a]] = 1;x] = sum;for (i = 1; i <= m; i++){//非常重要！概率为0，该状态可能无法到达，如果还去访问并建立方程会导致无解if (fabs (p) < eps) continue;v = (u + i) % n;if (has == -1) has = k++;a]] -= p;q.push (v);}}return flg;}int main(){int t, s, d, i;scanf ("%d", &t);while (t--){scanf ("%d%d%d%d%d", &n, &m, &e, &s, &d);n = 2*(n-1);sum = 0;for (i = 1; i <= m; i++){scanf ("%lf", p+i);p = p / 100;sum += p * i;}if (s == e){puts ("0.00");continue;}//一开始向左，起点要变if (d > 0) s = (n - s) % n;if (!bfs (s)){puts ("Impossible !");continue;}equ = var = k;Gauss ();printf ("%.2f\n", x]);} return 0;}
页:
[1]