codeforces 24d Broken robot 期望+高斯消元

题目传送门

题意：在n*m的网格上，有一个机器人从（x，y）出发，每次等概率的向右、向左、向下走一步或者留在原地，在最左边时不能向右走，最右边时不能像左走。问走到最后一行的期望。

思路：显然倒着算期望。

　　我们考虑既不是最后一行，也不靠边的一般方格，设$f[i][j]$为（i，j）这个格子的期望步数，显然有

　　$f[i][j]=\frac{1}{4}*(f[i][j-1]+f[i][j+1]+f[i+1][j]+f[i][j])+1$

　　移项有：$f[i][j]=\frac{1}{3}(f[i][j-1]+f[i][j+1]+f[i+1][j])+\frac{4}{3}$。

　　在我们处理处第i+1行所有的情况时，对于第i行，我们能得到像上述一样m个方程m个未知数，所以可以用高斯消元来解。

　　但是朴素的高斯消元是$n^3$的，显然会T，但是我们考虑此题的所有方程，写成行列式，会发现这个行列式只有对角线，和与对角线相邻的两行是有值的，这样按初中数学知识，就可以用$O（m）$的解除方程的解。

　　注意特别m=1的情况即可。

#pragma GCC optimize (2)

#pragma G++ optimize (2)

#pragma comment(linker, "/STACK:102400000,102400000")

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

#define dep(i,b,a) for(int i=b;i>=a;i--)

#define clr(a,b) memset(a,b,sizeof(a))

#define pb push_back

#define pii pair<int,int >

using namespace std;

typedef long long ll;

ll rd()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

const int maxn=;

double a[maxn][maxn],f[maxn][maxn],x[maxn];

int n,m,xx,yy;

void gauss(int id){

    for(int i=;i<=m;i++){

        double tmp=/a[i][i];

        a[i][i]*=tmp;

        x[i]*=tmp;

        if(i==m)break;

        a[i][i+]*=tmp;

        a[i+][i+]-=a[i][i+]*a[i+][i];

        x[i+]-=x[i]*a[i+][i];

        a[i+][i]=;

    }

    f[id][m]=x[m];

    for(int j=m-;j>;j--){

        x[j]-=a[j][j+]*x[j+];

        f[id][j]=x[j];

    }

}

int main(){

    cin>>n>>m>>xx>>yy;

    if(m==){

        printf("%d\n",(n-xx)*);

        return ;

    }

    for(int i=n-;i>=xx;i--){

        a[][]=,a[][]=-0.5,x[]=1.5+f[i+][]/;

        a[m][m]=,a[m][m-]=-0.5,x[m]=1.5+f[i+][m]/;

        for(int j=;j<m;j++){

            a[j][j]=;

            a[j][j-]=-1.0/;

            a[j][j+]=-1.0/;

            x[j]=f[i+][j]/+4.0/;

        }

        gauss(i);

    }

    printf("%.6f\n",f[xx][yy]);

}

巴特西

codeforces 24d Broken robot 期望+高斯消元

最新文章

热门文章