首页 > 代码库 > Hearthstone
Hearthstone
题意:
有$n$个无中生有,有$m$个不同的杀,第$i$个杀掉$X_i$滴血,敌人血量$P$,求问第一回合就将敌人杀死的概率是多少。
解法:
二进制枚举$A$类,$B$类卡的顺序,这样就确定了取了几个$B$卡,dp即可
$f(i,j)$表示选了$i$个卡,伤害和为$j$的方案数。
$ans = \sum {f(j,P)j!(m-j)!}$
总效率$O(n 2^{n+m})$
认真读题。
#include <iostream> #include <cstdio> #include <cstring> #define LL unsigned long long #define N 23 #define bit(x) (1<<(x)) using namespace std; int P, n, m; int X[N]; LL f[N][N][1010], comb[N][N], fac[N]; LL gcd(LL a, LL b) { if (b == 0) return a; return gcd(b, a % b); } int main() { comb[0][0] = 1; fac[0] = 1; for (int i = 1; i <= 20; i++) { fac[i] = fac[i-1] * i; comb[i][0] = 1; for (int j = 1; j <= i; j++) comb[i][j] = comb[i-1][j-1] + comb[i-1][j]; } int T; scanf("%d", &T); while (T--) { memset(f, 0, sizeof(f)); scanf("%d %d %d", &P, &n, &m); X[0] = 0; for(int i = 1; i <= m; i++) scanf("%d", &X[i]); f[0][0][0] = 1; for(int i = 0; i < m; i++) for(int j = 0; j <= i; j++) for(int k = P; k >= 0; k--) { f[i+1][j][k] += f[i][j][k]; f[i+1][j+1][min(k+X[i+1],P)] += f[i][j][k]; } LL ans0 = 0, ans1 = 0; for(int S=0;S<(1<<(n+m));S++) { int cnt=0,i,j=0; for(i=0;i<n+m;i++) if(bit(i)&S) cnt++; if(cnt!=m) continue; ans1 += fac[m]; cnt=1; for(i=0;i<n+m && cnt;i++) { if(bit(i)&S) cnt--, j++; else cnt++; } ans0 += f[m][j][P] * fac[m-j] * fac[j]; } if(ans0 == 0) { puts("0/1"); continue; } LL d = gcd(ans0, ans1); cout << ans0/d << ‘/‘ << ans1/d << endl; } return 0; }
Hearthstone
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。