BZOJ3191 [JLOI2013]卡牌游戏

2015.02.03 18:51 Tue| 0 visits oi_2015| 2015_刷题日常| Text

Solution

枚举每一个人,分别计算他的获胜概率:

令 f[i][j] 表示场上剩余 i 个人,距离庄家第 j 个人是当前考虑的人的概率。显然最后的 f[1][0] 就是我们想要求的答案。

只需要简单概率 DP 即可。详见短♂小的代码。

Code

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

#define N 55

int n, m, a[N];
double e[N][N];

double query(int x)
{
    memset(e, 0, sizeof e);
    e[n][x] = 1;
    for (int i = n - 1; i; e[i][0] = e[i][i], --i)
        for (int j = 0; j <= i; ++j)
            for (int k = 1; k <= m; ++k)
                e[i][(j + a[k] - 1) % (i + 1)] += e[i + 1][j] / m;
    return e[1][0];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        cin >> a[i];
    cout << fixed << setprecision(2);
    for (int i = 0; i < n; ++i)
        cout << query((n - i) % n) * 100 << '%' << " \n"[i == n - 1];
}