codeforces 24D---Broken robot 高斯消元求期望

题目链接：https://codeforces.com/problemset/problem/24/D

题目大意：给你一个$n imes m$的表格，初始的时候你位于$x,y$你现在有4种选择，待在原地，向左，向右，向下，每种选择的概率是一样的，问你到第n行的步数期望。

Examples

Input

10 10
10 4

Output

0.0000000000

Input

10 14
5 14

Output

18.0038068653

emmm，正着推推了老半天。。。感觉每次的概率期望DP都是倒着推的

我们用$f[i][j]$表示从第$i$行第$j$列到第n行的期望，由于是倒推的，那么每一行都只和左右下有关，那么对于每一行x则有表达式：

$f[x][j]=(f[x+1][j]+f[x][j+1]+f[x][j]) imes frac{1}{3}+1(j==1)$

$f[x][j]=(f[x+1][j]+f[x][j+1]+f[x][j-1]+f[x][j]) imes frac{1}{4}+1(j eq 1,j eq m)$

$f[x][j]=(f[x+1][j]+f[x][j-1]+f[x][j]) imes frac{1}{3}+1(j== m)$

变换可得：

$2f[x][j]-f[x][j+1]=3+f[x+1][j](j==1)$

$2f[x][j]-f[x][j-1]=3+f[x+1][j](j==m)$

$3f[x][j]-f[x][j-1]-f[x][j+1]=4+f[x+1][j](j eq 1,j eq m)$

由于是逆推的，所以上一行的每个期望都是知道的，即$C+f[x+1][j]$是个已知数。

那么由于有m列，所以右边就相当于是一个m行的列向量，那么左边就是m行m列的矩阵，我们可以用增广矩阵，那么也就是变成了m行m+1列的矩阵，然后进行高斯消元，可以看到的是，每行实际上只需要做两次减法就好了，不需要将整行都做一遍减法。

那么最后通过系数化为1，第m+1列就是枚举的x行的m各期望。下一次枚举的时候我们就可以直接用了。

以下是AC代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int mac=1e3+10;

double a[mac][mac],f[mac];
int n,m;

void solve(int x)
{
    memset(a,0,sizeof a);
    for (int i=1; i<=m; i++){
        if (i==1) {
            a[i][i]=2,a[i][i+1]=-1,a[i][m+1]=3+f[i];
            continue;
        }
        else if (i==m){
            a[i][i]=2,a[i][i-1]=-1,a[i][m+1]=3+f[i];
            continue;
        }

        a[i][i]=3,a[i][i+1]=-1,a[i][i-1]=-1,a[i][m+1]=4+f[i];
    }

    for (int i=1; i<m; i++){
        double p=a[i+1][i]/a[i][i];
        a[i+1][i]=0;
        a[i+1][i+1]-=a[i][i+1]*p;
        a[i+1][m+1]-=a[i][m+1]*p;
    }

    f[m]=a[m][m+1]/a[m][m];
    for (int i=m-1; i>=1; i--)
        f[i]=(a[i][m+1]-f[i+1]*a[i][i+1])/a[i][i];
}

int main()
{
    scanf ("%d%d",&n,&m);
    int st,ed;
    scanf ("%d%d",&st,&ed);
    if (m==1) {printf("%.10f
",2.0*(n-st)); return 0;}
    for (int i=n-1; i>=st; i--){
        solve (i);//对每行高斯消元
    }
    printf("%.10f
",f[ed]);
    return 0;
}