[置顶] hdu 4418 高斯消元解方程求期望

题意:

一个人在一条线段来回走(遇到线段端点就转变方向)，现在他从起点出发，并有一个初始方向，

每次都可以走1, 2, 3 ..... m步，都有对应着一个概率。问你他走到终点的概率

思路：

方向问题很是问题，我们可以把线段改造成环，具体我们可以把除端点以外的点作为另一个半圆和原来的线段拼成一个环，

方向就单一了，用dp[i]表示在i点的时候到达终点的期望步数，则dp[i]=dp[(i+1)%N]*p1+E[(i+2)%N]*p2+…E[(i+m)%N]*pm+1。

这里N为变成环以后的点数。注意到有些点是无法到达的，自然这些点的期望是无意义的，可以理解成正无穷，在实际列方程的时候，我们不需要把这些点列入方程中去，这样避免解方程的时候出现问题。所以我们可以先从起点进行bfs，将能到达的点进行标号，搜完后，有标号的点都是方程的未知数。然后对每个能到达的点列一个方程，高斯消元解出dp[起点]就是答案。

代码：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 203;
const double  eps = 1e-9;
//高斯消元白书模板
//n ： 未知数个数，   a[][]为增广矩阵
//把解放在    a[][n]中
bool gauss(double a[][maxn], int n) {
    int i, j, k, r;
    for (i = 0; i < n; i++) {
        r = i;
        for (j = i + 1; j < n; j++)
            if (fabs(a[j][i]) > fabs(a[r][i]))
                r = j;

        if (fabs(a[r][i]) < eps)
            return 0;

        if (r != i)
            for (j = 0; j <= n; j++)
                swap(a[r][j], a[i][j]);


		//根据精度需要选择以下其一：
        //低精度
        for (k = i + 1; k < n; k++) {
            r = a[k][i] / a[i][j];
            for (j = i; j <= n; j++)
                a[k][j] -= r * a[i][j];
        }
        //

        //高精度
        for (j = n; j >= i; j--)
            for (k = i + 1; k < n; k++)
                a[k][j] -= a[k][i] / a[i][i] * a[i][j];
        //
    }

	//回代过程
    for (i = n - 1; i >= 0; i--) {
        for (j = i + 1; j < n; j++)
            a[i][n] -= a[j][n] * a[i][j];
        a[i][n] /= a[i][i];
    }
    return 1;
}
int n, m, t, s, d, N;
double p[103];
int idx[maxn], id;   //idx给能到达的点标号，id为能到达的点的个数，也是方程未知数的个数
void bfs(int s) {
    id = 0;
    memset(idx, -1, sizeof(idx));
    queue<int> q;
    q.push(s);
    idx[s] = id++;
    int i;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (i = 1; i <= m; i++) {
            if (fabs(p[i]) < eps)
                continue;
            int v = (u + i) % N;
            if (idx[v] == -1) {
                idx[v] = id++;
                q.push(v);
            }
        }
    }
}
double a[maxn][maxn];
//s起点  t终点
int main() {
    int i, j, cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d%d%d%d", &n, &m, &t, &s, &d);
        for (i = 1; i <= m; i++) {
            scanf("%lf", &p[i]);
            p[i] /= 100;
        }
        if(s == t) {    //必须特判
            printf("0.00
");
            continue;
        }
        N = (n - 1) << 1;
        if (d == 1) s = N - s;

        bfs(s);
        if (idx[t] == -1 && idx[N-t] == -1) {
            printf("Impossible !
");
            continue;
        }
		//id变成了方程组未知数的个数
        memset(a, 0, sizeof(a));
        for(i = 0; i < N; i++)
            if(~idx[i]) {
                a[idx[i]][idx[i]] = 1;
                if(i == t || i == N-t)
                    continue;
                for(j = 1; j <= m; j++) {
                    int v = (i+j)%N;
                    if(idx[v] != -1) {
                        a[idx[i]][idx[v]] -= p[j];
                        a[idx[i]][id] += j*p[j];
                    }
                }
            }
        if(gauss(a, id)) printf("%.2f
", a[idx[s]][id]);
        else printf("Impossible !
");
    }
    return 0;
}

[置顶] hdu 4418 高斯消元解方程求期望

相关推荐