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 
#include 
#include #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;iif(bit(i)&S) cnt++;if(cnt!=m) continue;ans1 += fac[m];cnt=1;for(i=0;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;
}

View Code