Description

link

(n(nle50)) 个人坐在一圈，有 (m(mle 50)) 张牌，每个人每轮随机抽一张，数字是(k)

以该人为第一个，顺时针第(k) 个出局

求每个人在进行完 (n-1) 轮后胜利的概率

Solution

先定义状态：(f_{i,j}) 为(i) 个人做游戏，第 (j) 个最终获胜的概率

起始态：(f_{1,1}=1) （含义）

目标态：(f_{n,p},ple n)

转移：

[f_{i,j}=sum_{k=1}^m f_{i-1,j-d[k]} ]

这里(d_k) 是牌上的数字，(j-d_k)需要考虑是负数的情况（加个 (i) 就行了）

讲讲想法：

是个逆推的思想，正推的做法……

我们看第 (j) 个人拿到一张牌能干掉谁，

那个人再如果没有这一轮是赢的，所以 (j) 干掉了他也就赢了

本题就完结了

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=101;
	double f[N][N];
	int n,m,a[N];
	signed 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<=i;++j)
			{
				for(int k=1;k<=m;++k)
				{
					int t=a[k]%i; if(!t) t=i;
					if(t>j) f[i][j]+=f[i-1][i-t+j]/m;
					if(t<j) f[i][j]+=f[i-1][j-t]/m;
				}
			}
		}
		for(int i=1;i<=n;++i) printf("%.2lf\% ",f[n][i]*100); puts("");
		return 0;
	}
}
signed main(){return yspm::main();}

Review

对于有些可 (dfs) 的题目，可以考虑用一下记忆化或者类似从结果开始记录答案的思想

感觉这个题是个好题，但是百分号输出就有时候不太地道