題目鏈接：卡牌游戲
n個人，m張卡牌上有m個數字，莊家隨機一張卡牌，數字為X，第X位出局，隨后第X位的下一位做莊家，問，每個人最后獲勝的概率是多少？
約瑟夫環的變形問題，這里每次等概率的抽牌，數字是隨機的，
dp[i][j]: 還剩i個人時，第j個人獲勝的概率 ，
dp[1][1]=1.0 最后剩下的那個人獲勝
從游戲的結局向前推，剩i人時，列舉m張卡牌，計算出下一局他的位置（也就是剩i-1人時），累加，我們算的是第j個人獲勝的概率，如果剛好抽到他自己出局，忽略，
抽到出局的位置temp：
1，temp=j ，忽略
2，temp < j 時，他下一局的位置 j-temp；累加 dp[i-1][j-temp]
3，temp > j 時，他下一局的位置 i-temp+j；累加 dp[i-1] [i-temp+j]
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int maxx=100;
double dp[maxx][maxx];
int a[maxx];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++)
scanf("%d",&a[i]);
dp[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 temp=a[k]%i==0 ? i:a[k]%i;
if(temp>j)
dp[i][j]+=(dp[i-1][i-temp+j]/(double)m);
else if(temp<j)
dp[i][j]+=(dp[i-1][j-temp]/(double)m);
}
char ch='%';
for(int i=1;i<=n;i++)
printf("%.2lf%c ",dp[n][i]*100,ch);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/325846.html
標籤：其他
上一篇：Unity 人物上坡貼地移動
下一篇：Unity-瓦片地圖詳解