织梦后台发布了网站没显示,建设个人网页登陆网站,苏州设计公司北京vi设计公司,采购需求发布平台【概率DP】P2059 卡牌游戏 链接 题目描述 N个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从1到N编号。首先第一回合是玩家1作为庄家。每个回合庄家都会随机#xff08;即按相等的概率#xff09;从卡牌堆里选择一张卡片#xff0c;假设卡片上的数字为X#xff0c;则庄… 【概率DP】P2059 卡牌游戏 链接 题目描述 N个人坐成一圈玩游戏。一开始我们把所有玩家按顺时针从1到N编号。首先第一回合是玩家1作为庄家。每个回合庄家都会随机即按相等的概率从卡牌堆里选择一张卡片假设卡片上的数字为X则庄家首先把卡片上的数字向所有玩家展示然后按顺时针从庄家位置数第X个人将被处决即退出游戏。然后卡片将会被放回卡牌堆里并重新洗牌。被处决的人按顺时针的下一个人将会作为下一轮的庄家。那么经过N-1轮后最后只会剩下一个人即为本次游戏的胜者。现在你预先知道了总共有M张卡片也知道每张卡片上的数字。现在你需要确定每个玩家胜出的概率。 输入格式 第一行包括两个整数N,M分别表示玩家个数和卡牌总数。 接下来一行是包含M个整数分别给出每张卡片上写的数字。 输出格式 输出一行包含N个百分比形式给出的实数四舍五入到两位小数。分别给出从玩家1到玩家N的胜出概率每个概率之间用空格隔开最后不要有空格。 样例】 5 5
2 3 5 7 11 22.72% 17.12% 15.36% 25.44% 19.36% 4 4
3 4 5 6 25.00% 25.00% 25.00% 25.00% 对于30%的数据有\(1 \leq N \leq 10\) 对于50%的数据有\(1 \leq N \leq 30\) 对于100%的数据有1 \(\leq\) N \(\leq\) 50, 1 \(\leq\) M \(\leq\) 50 ,1 \(\leq\)每张卡片上的数字\(\leq\) 50 Solution 其实这题一开始我一点思路都没有。开始想着正着搜但似乎要记录很多东西想了想转移不可行。那……倒着搜 设f[i][j]为有i个人的时候第j个人胜利的概率。因为概率可以相加所以可以往后推。 如何转移手推一下发现在有i个人的情况下庄家抽到牌k那么在i - 1个人中第j个人的位置是……分类讨论。若 k jj j - k 若k j j i - k j若k j不用考虑因为j死了。 所以转移方程长这样 int p a[k] % i 0? i:a[k] % i;
if(p j) f[i][j] f[i - 1][i - p j] / m;
else if(p j) f[i][j] f[i - 1][j - p] / m; \(Thats~~all\) #include iostream
#include cstring
#include cstdio
using namespace std;
long long read(){long long x 0; int f 0; char c getchar();while(c 0 || c 9) f | c -, c getchar();while(c 0 c 9) x (x 3) (x 1) (c ^ 48), c getchar();return f? -x:x;
}int n, m, a[57];
double f[57][57];
int main(){n read(); m read();for(int i 1; i m; i) a[i] read();f[1][1] 1.0;for(int i 2; i n; i)for(int j 1; j i; j)for(int k 1; k m; k){int p a[k] % i 0? i:a[k] % i;if(p j) f[i][j] f[i - 1][i - p j] / m;else if(p j) f[i][j] f[i - 1][j - p] / m;}printf(%.2lf%%, f[n][1] * 100);for(int i 2; i n; i) printf( %.2lf%%, f[n][i] * 100);return 0;
} 转载于:https://www.cnblogs.com/kylinbalck/p/11260150.html
