一道不错的线性 dp,带了点逆推。
注意到如果我们设 \(f_{i,j}\) 表示前 \(i\) 轮过后 \(j\) 存活的概率,那么我们需要额外记录哪些人无了,否则无法转移。
考虑这样一件事:无论剩下来哪些玩家,如果我们重新编号,庄家编号为 1,剩下的为 2,3,4....,那么每个人胜率其实是固定的,不会因为哪些玩家被淘汰而改变,并且这个胜率只会和之后游戏情况有关,与之前游戏情况没关系。
据此,我们考虑设 \(f_{i,j}\) 表示从第 \(n\) 轮到第 \(n-i+1\) 轮,将庄家重编号为 1,剩下的为 2,3,4... 之后,编号为 \(j\) 的人的胜率是多少。显然初值 \(f_{1,1}=1\),所求答案即 \(f_{n,i}\)。
考虑如何转移,每次我们枚举当前使用了哪一张牌,设为 \(a_j\),那么显然 \(a_j\bmod i\)(如果为 0 就置为 \(i\))这个人会被淘汰,从 \((a_j\bmod i)+1\) 这个人开始,会顺次成为下一轮的庄家,2 号,3 号...,对应的胜率就是 \(f_{i-1,1},f_{i-1,2},f_{i-1,3}...\),加上去即可,注意由于我们枚举了当前使用的牌,这里还有 \(\dfrac{1}{m}\) 的概率,因此实际要加上的概率是 \(\dfrac{1}{m}f_{i-1,1},\dfrac{1}{m}f_{i-1,2}...\)。
最后不要忘记用百分数形式输出即可。
Code:
/*
========= Plozia =========
Author:Plozia
Problem:P2059 [JLOI2013] 卡牌游戏
Date:2022/10/19
========= Plozia =========
*/
#include <bits/stdc++.h>
typedef long long LL;
const int MAXN = 50 + 5;
int n, m, a[MAXN];
double f[MAXN][MAXN];
int Read()
{
int sum = 0, fh = 1; char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * fh;
}
int main()
{
n = Read(), m = Read(); for (int i = 1; i <= m; ++i) a[i] = Read();
f[1][1] = 1;
for (int i = 2; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
int p = a[j] % i;
for (int k = 1; k < i; ++k)
{
p = p % i + 1; f[i][p] += f[i - 1][k] / m;
}
}
for (int i = 1; i <= n; ++i) printf("%.2lf%% ", f[n][i] * 100);
puts(""); return 0;
}
标签:...,ch,JLOI2013,游戏,int,题解,胜率,MAXN,P2059
From: https://www.cnblogs.com/Plozia/p/16807572.html