题解：[Algo Beat Contest 002 D] Distance of Trip

zhoumurui · 2025-03-29 08:28:42 · 题解

题面简述

解题思路

令 f_{x,y,z} 表示 Cirno 在 第 z 秒恰好走到 (x,y) 的概率。

考虑动态规划。如果 Cirno 在第 z 秒走到了 (x,y)，那么它在第 z-1 秒可能在 (x,y-1)、(x-1,y) 或 (x-1,y-1)。

当她在这些位置的时候，各有 \frac{1}{3} 的概率来到 (x,y)。

因此状态转移方程是 f_{x,y,z}=\frac{1}{3}(f_{x-1,y,z-1}+f_{x,y-1,z-1}+f_{x-1,y-1,z-1})。

期望是试验中每次可能结果的概率乘以其结果的总和。

我们想要计算 Cirno 到达的位置与起点直线距离的期望值。那么我们只需要枚举所有 Cirno 可能到达的位置即可。

她每秒最多往东走一格，往南走一格，那么她可能到达的位置 (x,y) 一定满足 0 \le x,y \le T。

我们在这个范围内枚举所有的 (x,y)，加上 Cirno 在 T 秒后恰好来到 (x,y) 的概率即 f_{x,y,T} 乘上 (x,y) 到起点的直线距离即 \sqrt{x^2+y^2} 即可。

核心代码展示

dp 时要判越界。

double f[205][205][205];
signed main(){
    int t;
    cin>>t;
    f[0][0][0]=1;
    for (int i=1;i<=t;i++){
        for (int j=0;j<=t;j++){
            for (int k=0;k<=t;k++){
                if (j>0)f[j][k][i]+=f[j-1][k][i-1];
                if (k>0)f[j][k][i]+=f[j][k-1][i-1];
                if (j>0&&k>0)f[j][k][i]+=f[j-1][k-1][i-1];
                f[j][k][i]/=3.0;
            }
        }
    }
    double ans1=0;
    for (int i=0;i<=t;i++){
        for (int j=0;j<=t;j++){
            //cout<<i<<" "<<j<<" "<<f[i][j][t]<<"\n";
            ans1+=f[i][j][t]*sqrt(i*i+j*j);
        }
    }
    printf("%.10lf",ans1);
    return 0;
}