M_sea

CF24D Broken robot
CodeForcesLuogu算法设$f[i][j]$表示$(i,j)$到最后一排的移动步数的期望。容易得出:$f...
扫描右侧二维码阅读全文
31
2018/08

CF24D Broken robot

CodeForces

Luogu

算法

设$f[i][j]$表示$(i,j)$到最后一排的移动步数的期望。

容易得出:

$f[i][1]=\frac{1}{3}(f[i][1]+f[i][2]+f[i-1][1])+1$

$f[i][m]=\frac{1}{3}(f[i][m]+f[i][m-1]+f[i-1][m])+1$

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

发现列与列的转移是有后效性的。

所以用有后效性DP的基本方法——DP套高斯消元。

但是发现系数矩阵中每行只有几个数要消,而且非常有规律。所以可以$O(m)$解。

细节见代码。注意要特判$m=1$的情况。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m,X,Y;
double f[1010][1010];

double a[1010][1010];
double b[1010];

inline void Build(int R) {
    if (m==1) {
        a[1][1]=-1.0/2.0;
        b[1]=-f[R+1][1]/2.0-1;
        return;
    }
    a[1][1]=a[m][m]=-2.0/3.0,a[1][2]=a[m][m-1]=1.0/3.0;
    b[1]=-f[R+1][1]/3.0-1,b[m]=-f[R+1][m]/3.0-1;
    for (re int i=2;i<m;i++) {
        a[i][i-1]=a[i][i+1]=1.0/4.0,a[i][i]=-3.0/4.0;
        b[i]=-f[R+1][i]/4.0-1;
    }
}

inline void Guass(int R) {
    for (re int i=1;i<m;i++) {
        double rate=a[i+1][i]/a[i][i];
        a[i+1][i]-=rate*a[i][i];
        a[i+1][i+1]-=rate*a[i][i+1];
        b[i+1]-=rate*b[i];
    }
    f[R][m]=b[m]/a[m][m];
    for (re int i=m-1;i>=1;i--) f[R][i]=(b[i]-f[R][i+1]*a[i][i+1])/a[i][i];
}

int main() {
    n=read(),m=read(),X=read(),Y=read();
    for (re int i=n-1;i>=X;i--) { Build(i); Guass(i); }
    printf("%.10f\n",f[X][Y]);
    return 0;
}
最后修改:2018 年 12 月 26 日 08 : 55 PM

发表评论