洛谷2059 [JLOI2013]卡牌游戏

Luogu

算法

概率DP。

设$f[i][j]$表示还剩i个人时第j个人的获胜概率。

边界显然是$f[1][1]=1.0$。
那么状态如何转移呢?

我们可以首先枚举庄家抽到的卡牌$k$,得到这一轮被淘汰的人的位置$c$。当然,如果$c=j$,就不要考虑了(因为这表示此轮第$j$个人被淘汰)。

而第$c$个人被淘汰之后,剩下的$i-1$个人要组成一个新的环,庄家为第$c$个人的下一个。容易算出,当$c>j$时,第$j $个人是新的环里从新庄家数起的第$i-c+j$个人,当$c<j$时,第$j$个人是新的环里从新庄家数起的第$j-c$个人。

所以$f[i][j]+=\begin{cases}f[i-1][j-c]/m&(c<j)\\0&(c=j)\\f[i-1][i-c+j]/m&(c>j)\end{cases}$

注意到$j=c$时是不用计算的。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;
double f[60][60]; //f[i][j]表示还剩i个人时第j个人的获胜概率 
int num[60];
int main() {
    int n,m; scanf("%d%d",&n,&m);
    for (re int i=1;i<=m;i++) scanf("%d",&num[i]);
    f[1][1]=1.0;
    for (re int i=2;i<=n;i++)
        for (re int j=1;j<=n;j++)
            for (re int k=1;k<=m;k++) {
                int c=(num[k]%i) ? num[k]%i : i;
                if (c<j) f[i][j]+=f[i-1][j-c]/m;
                else if (c>j) f[i][j]+=f[i-1][i-c+j]/m;
            }
    for (re int i=1;i<=n;i++) printf("%.2lf%% ",f[n][i]*100.0);
    return 0;
}
最后修改:2019 年 09 月 24 日 12 : 58 PM

3 条评论

  1. xgzc

    转移写错啦

    1. M_sea
      @xgzc

      已修改。

      窝以前是怎么写错的。。

  2. ZCDHJ

    我都不会算概率

发表评论