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

· · 题解

思路：

看完题目后，应该都能知道这是一道 DP 题。

设状态

设 dp_{i,j,k} 表示第 k 秒后，在 (x,y) 的概率。

设转移

如果当前位置为 (x,y) 的话，那么，按照题目的做法，一共有三种走法，如此，把每种走法都加到一起，再乘一个 \frac{1}{3} 就是走到当前位置的概率。

则有转移状态：

dp_{i,j,k} = \frac{1}{3}(dp_{x−1,y,z−1}+dp_{x,y−1,z−1}+f_{x−1,y−1,z−1})

接下来，枚举每个位置，求出到这个位置的概率，最后求和就可以了。

代码：

#include<bits/stdc++.h>
using namespace std;
double dp[210][210][210],ans;
int n;
signed main(){
    scanf("%d",&n),dp[0][0][0] = 1;
    for (int i = 1;i <= n;i++)
        for (int j = 0;j <= n;j++)
            for (int k = 0;k <= n;k++){
                if (j > 0) dp[j][k][i] += dp[j - 1][k][i - 1];
                if (k > 0) dp[j][k][i] += dp[j][k - 1][i - 1];
                if (j > 0 && k > 0) dp[j][k][i] += dp[j - 1][k - 1][i - 1];
                dp[j][k][i] /= 3.0;
            }
    for (int i = 0;i <= n;i++)
        for (int j = 0;j <= n;j++) ans += dp[i][j][n] * sqrt(i * i + j * j);
    printf("%.9lf\n",ans);
}