[JLOI2013] 卡牌游戲

首先我們對題目進行觀察發現，在我們進行選牌的時候會在特定輪回中槍斃一個人，隨后，進行下一輪

我們會很自然的想到dp，但是，如果從頭開始順，會發現后面的每一種情況都會影響到前面的狀態，這樣就違反了我們進行DP的初心，甚至樸素做法會比DP更省時間

這怎么辦呢?我們舉一個栗子：牌為1,2,3,4,5

如果只剩一個人，那么這個人的勝率是百分之百

如果剩兩個人，那么選到1,3,5時候，莊獲勝，否則另一個人獲勝，即：莊勝率為$ \frac 3 5$ ,二號勝率為 $\frac 2 5$

...

由此，我們不難看出，從后往前推的時候，每次狀態轉移并不會影響先前的狀態，就可以進行很好的狀態轉移

#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
double f[maxn][maxn];
int ma[maxn];
int n,m;
int main()
{
	cin>>n>>m;
	f[1][1]=1.0;
	for(int i=1;i<=m;i++)
	{
		cin>>ma[i];
	}
	for(int i=2;i<=n;i++)
	{
		for(int k=1;k<=m;k++)
		{
			int p=(ma[k]%i==0)?i:ma[k]%i;
			for(int j=1;j<=i-1;j++)
			{
				++p;
				p=(p>i)?1:p;
				f[i][p]+=f[i-1][j]/(double)(m);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		printf("%.2lf%% ",f[n][i]*100.00);
	}
	
}