GG给的题目系列 (好像是唯一一道题)
总体来讲dp其实就是(NOIP)
线性 状压 树上 数位 期望
完了想好矩阵优化和单调队列就稳了
剩下的就积极地想状态 理清思路
最关键的就是最优子结构和无后效性 然后就可以合理猜
(假装自己做完了dp总结)
这个题就是直接堆概率
f[i][j]表示i个人从庄家数第j个胜率(庄家算1)
枚举m个牌判断出局的人更新就好了
注意特判==的情况= =
time cost:35min
Code:
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<queue>
5 #define ms(a,b) memset(a,b,sizeof a)
6 #define rep(i,a,n) for(int i = a;i <= n;i++)
7 #define per(i,n,a) for(int i = n;i >= a;i--)
8 #define inf 1000000007
9 using namespace std;
10 typedef long long ll;
11 typedef double D;
12 #define eps 1e-2
13 ll read() {
14 ll as = 0,fu = 1;
15 char c = getchar();
16 while(c < '0' || c > '9') {
17 if(c == '-') fu = -1;
18 c = getchar();
19 }
20 while(c >= '0' && c <= '9') {
21 as = as * 10 + c - '0';
22 c = getchar();
23 }
24 return as * fu;
25 }
26 //head
27 const int N = 55;
28 int n,m;
29 int a[N];
30 D dp[N][N];
31
32 int main() {
33 n = read(),m = read();
34 rep(i,1,m) a[i] = read();
35 ms(dp,0);
36 dp[1][1] = 1.00;
37 rep(i,2,n) rep(j,1,i) rep(k,1,m) {
38 int c = ((a[k] % i) ? (a[k] % i) : i);
39 if(c > j) c = i - c + j;
40 else if(c < j) c = j - c;
41 else c = 0;
42 dp[i][j] += dp[i-1][c] / (D)m;
43 }
44 rep(i,1,n) printf("%.2lf%% ",dp[n][i] * 100.00);
45 puts("");
46 return 0;
47 }