洛谷2059 [JLOI2013]卡牌游戏

题意

有 $n(\le 50)$ 个人用 $m(\le 50)$ 张卡牌玩游戏。第一局由玩家 $1$ 坐庄抽卡，如果卡上的数字是 $x$ ，那么从他的位置数第 $x$ 的人就被处决。第二局就由被处决的人的后一个人坐庄，以此类推，最后剩下的玩家获得胜利。求每个玩家的胜率。

题解

概率DP，用 $f[i][j]$ 表示还剩 $i$ 个人，从坐庄的人往后数第 $j$ 个人的胜率。

如果只剩 $1$ 个人，那么他获得胜利，所以初值为 $f[1][1]=1$ 。

可以发现 $f[i]$ 可以从 $f[i-1]$ 转移过来。枚举抽的卡 $k$ ，就可以算出这一局被淘汰的人，从而可以得到第 $j$ 个人在下一局里的位置 $nxt$。如果抽这张卡时 $j$ 活了下来，那么 $j$ 在这局中获胜的概率就增加了 $\frac{f[i-1][nxt]}{m}$ 。转移方程式为：

$$f[i][j]=\sum \dfrac{f[i-1][nxt]}{m}$$

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=55;
int n,m,s[N];
double f[N][N];

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++) s[i]=read();
    f[1][1]=1;
    for (int i=2;i<=n;i++)
    {
        for (int j=1;j<=i;j++)
        {
            for (int k=1;k<=m;k++)
            {
                int cur=s[k]%i ? s[k]%i : i; //被淘汰的人
                int nxt=cur<j ? j-cur : j-cur+i; //j在下一局的位置
                f[i][j]+=f[i-1][nxt]/m;
            }
        }
    }
    for (int j=1;j<=n;j++) printf("%.2f%% ",f[n][j]*100);
    return 0;
}