《算法竞赛进阶指南》0x55环形与后效性处理DP Acwing290 坏掉的机器人

题目链接：https://www.acwing.com/problem/content/292/

题目给定n,m,表示一个m*n的图，和x，y，问从(x,y)出发走到最后一行的步数的数学期望，走法是随机走到左右，下面或者不动。

期望可以线性叠加，但是阶段却只有行是无后效性的，考虑到转移方式的不变性，M个方程M个未知数，而且数学期望一定是唯一且存在的，所以可以通过高斯消元法求。

但是朴素的高斯消元法是O(n^3)的，本题有一个特点就是矩阵非常稀疏，可以在O(M)时间内变换增广矩阵，通过从最后一行进行n-1轮递推便得到了最终的结果。

高斯消元，经典方式：先找主元（本题中不需要）、归一化、消下一行、变成上对角矩阵、然后从最后一行开始变成对角矩阵，这样解也会随着计算得出，一轮的时间是O(M)

在只有一列的情况下没法消元，通过等差数列求出即可。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn = 1010;
double a[maxn][maxn];
double f[maxn][maxn];
int n,m;
int x,y;
void gauss(){
    for(int i=1;i<=m;i++){
        double r=a[i][i];
        a[i][i]/=r,a[i][i+1]/=r;
        if(i<m)a[i][m+1]/=r;//最有一行只有两个数要除
        double t=a[i+1][i];
        int d[3]={i,i+1,m+1};
        for(int j=0;j<3;j++){//变成上三角矩阵 
            a[i+1][d[j]]-=t*a[i][d[j]];
        }
    }
    
    for(int i=m;i>1;i--){//消去副对角线 
        a[i-1][m+1]-=a[i-1][i]*a[i][m+1];
        a[i-1][i]-= a[i-1][i]*a[i][i];
    } 
}
int main(){
    cin>>n>>m;
    cin>>x>>y;
    if(m==1)printf("%.4lf",2*(n-x));
    else{
        for(int i=n-1;i>=x;i--){
            a[1][1]=2.0/3,a[1][2]=-1.0/3,a[1][m+1]=f[i+1][1]*1.0/3+1;
            a[m][m-1]=-1.0/3,a[m][m]=2.0/3,a[m][m+1]=f[i+1][m]*1.0/3+1;
            for(int j=2;j<m;j++){
                a[j][j-1]=-1.0/4,a[j][j]=3.0/4;
                a[j][j+1]=-1.0/4,a[j][m+1]=1.0/4*f[i+1][j]+1;
            }
        gauss();
        
        for(int j=1;j<=m;j++)f[i][j]=a[j][m+1];
        }
        
        printf("%.4lf",f[x][y]);
    }
    
    return 0;
}

《算法竞赛进阶指南》0x55环形与后效性处理DP Acwing290 坏掉的机器人

相关推荐