• 作者:zifeiy
  • 标签:概率DP

题目链接:https://www.luogu.org/problem/P2719

我们设 f[n][m] 用于表示还剩下n张A类票m张B类票时最后两张票相同的概率,则:

  • 如果 \(n \le 1\)\(m \le 1\) ,则 \(f[n][m] = 0\) (凑不齐两张一样的)
  • 否则,如果 \(n == 0\) 或者 \(m == 0\),则 \(f[n][m] = 1\) (肯定是一样的两张票)
  • 否则,\(f[n][m] = (f[n-1][m] + f[n][m-1]) \times 0.5\) (有一半的概率拿走一张A类票,另一半的概率拿走一张B类票)

所以我们可以按照如下思路编写代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1300;
double f[maxn][maxn];
int n;

int main() {
    scanf("%d", &n);
    n /= 2;
    for (int i = 0; i <= n; i ++) {
        for (int j = 0; j <= n; j ++) {
            if (i < 2 && j < 2) f[i][j] = 0.;
            else if (i == 0 || j == 0) f[i][j] = 1.;
            else f[i][j] = 0.5 * (f[i-1][j] + f[i][j-1]);
        }
    }
    printf("%.4lf\n", f[n][n]);
    return 0;
}

记忆化搜索方式写的代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1300;
bool vis[maxn][maxn];
double f[maxn][maxn];
int n;

double dfs(int n, int m) {
    if (vis[n][m]) return f[n][m];
    vis[n][m] = true;
    if (n <= 1 && m <= 1) return 0.;
    if (n == 0 || m == 0) return 1.;
    f[n][m] = 0.5 * (dfs(n-1, m) + dfs(n, m-1));
    return f[n][m];
}

int main() {
    scanf("%d", &n);
    n /= 2;
    printf("%.4lf\n", dfs(n, n));
    return 0;
}
02-13 15:26