高斯消元解機率動态規劃

@(E ACMer)

題目抽象:

一個長度為 100 的由格子組成的路，你開始在 1 号格子，求你走到100号格子的期望步數？

行走規則如下：

- 你有一個六面的刻有數字 [1,6] 的等機率骰子，每次抛出骰子，上面顯示的數字就是你走的步數。

- 但是有一些類似 (x,y) 的規則表示：你一旦跳到了 x 号格子，你就會瞬間走回y号格子，且這個跳躍不算做步數。(注意這裡的x可能小于y)。

分析：

令 jump(i) 表示：從 i 會立即跳躍到jump(i)，對于沒有跳躍規則的格子 jum(i)==i ，令 f(i) ：表示從 i 走到100的期望步數，我們的目的就是求 f(1) 。

如果 y>=x ，那麼這個問題很好求解:

f(i)=6+∑j<=6 and i+j<=100j=1f(jump(i+j)+t∗f(i)6

if (t>94) t=(6−100−i)  else  t=0

直接動态規劃求解即可。

但是這裡 y<x 的情況存在，就會出現循環的情況，無法遞推。我們隻能列出含有100個未知變量的100個機率方程，然後用解線性方程組的高斯消元方法求解。

構造方程的其中一項類似：

6xi−xi+1−xi+2−....−xi+6=6

複雜度主要是高斯消元的複雜度 O(1003)

code:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define pr(x) cout << #x << ": " << x << "  " 
#define pl(x) cout << #x << ": " << x << endl;
const int maxn = ;
const double eps = ;

double a[maxn][maxn], ans[maxn];
int jump[maxn << ];


void gauss(void) {
    int i, j, t, k;
    for (i = ; i <= ; i++) {
        t = i;
        for (j = i + ; j <= ; j++) if (a[t][i] < a[j][i]) t = j;
        if (t != i) for (j = ; j <= ; j++) swap(a[i][j], a[t][j]);
        if (fabs(a[i][i]) < eps) continue;
        for (j = i + ; j <= ; j++) {
            if (fabs(a[j][i]) > eps) {
                double tt = a[j][i] / a[i][i];
                for (k = i; k <= ; k++) a[j][k] -= a[i][k] * tt;
            }
        }
    }
    for (i = ; i >= ; i--) {
        for (j = ; j > i; j--) a[i][] -= a[i][j] * ans[j];
        if (fabs(a[i][i] > eps)) ans[i] = a[i][] / a[i][i];
        if (fabs(a[i][i]) < eps) ans[i] = ;
    }
}

void build_a(void) {
    memset(ans, , sizeof(ans));
    memset(a, , sizeof(a));
    for (int i = ; i <= ; i++) {
        a[i][i] = a[i][] = ;
        for (int j = ; j <= ; j++) {
            if (i + j > ) a[i][i] -= ;
            else a[i][jump[i + j]] += -;
        }
    }
}

int main()
{
#ifdef LOCAL 
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int T, N;
    scanf("%d", &T);
    for (int cas = ; cas <= T; cas++) {
        scanf("%d", &N);
        for (int i = ; i <= ; i++) jump[i] = i;
        for (int i = ; i < N; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            jump[x] = y;
        }
        build_a();
        gauss();
        printf("Case %d: %.15f\n", cas, ans[]);
    }
    return ;
}