---恢复内容开始---
Hearthstone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1102 Accepted Submission(s): 544
Now you are asked to calculate the probability to become a "Shen Chou Gou" to kill your enemy in this turn. To simplify this problem, we assume that there are only two kinds of cards, and you don't need to consider the cost of the cards.
-A-Card: If the card deck contains less than two cards, draw all the cards from the card deck; otherwise, draw two cards from the top of the card deck.
-B-Card: Deal X damage to your enemy.
Note that different B-Cards may have different X values.
At the beginning, you have no cards in your hands. Your enemy has P Hit Points (HP). The card deck has N A-Cards and M B-Cards. The card deck has been shuffled randomly. At the beginning of your turn, you draw a card from the top of the card deck. You can use all the cards in your hands until you run out of it. Your task is to calculate the probability that you can win in this turn, i.e., can deal at least P damage to your enemy.
Then come three positive integers P (P<=1000), N and M (N+M<=20), representing the enemy’s HP, the number of A-Cards and the number of B-Cards in the card deck, respectively. Next line come M integers representing X (0<X<=1000) values for the B-Cards.
---恢复内容结束---
Hearthstone
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1102 Accepted Submission(s): 544
Now you are asked to calculate the probability to become a "Shen Chou Gou" to kill your enemy in this turn. To simplify this problem, we assume that there are only two kinds of cards, and you don't need to consider the cost of the cards.
-A-Card: If the card deck contains less than two cards, draw all the cards from the card deck; otherwise, draw two cards from the top of the card deck.
-B-Card: Deal X damage to your enemy.
Note that different B-Cards may have different X values.
At the beginning, you have no cards in your hands. Your enemy has P Hit Points (HP). The card deck has N A-Cards and M B-Cards. The card deck has been shuffled randomly. At the beginning of your turn, you draw a card from the top of the card deck. You can use all the cards in your hands until you run out of it. Your task is to calculate the probability that you can win in this turn, i.e., can deal at least P damage to your enemy.
Then come three positive integers P (P<=1000), N and M (N+M<=20), representing the enemy’s HP, the number of A-Cards and the number of B-Cards in the card deck, respectively. Next line come M integers representing X (0<X<=1000) values for the B-Cards.
暴力做法，我们枚举所有可能出现的集合，dp[S]表示S中的元素可组成的排列组合个数。
计算dp数组时采用的是我为人人型递推，if当前集合伤害大于P，或者没有抽牌的能力直接continue;
否则枚举所有他可能抽到的牌对新产生的集合(当前集合加上新抽的牌)加上当前集合的方案数；
之后遍历所有集合，如果这个集合造成的伤害大于等于P，就把dp[i]*f[N-|S|]加入分子，最后分母为(n+m)!;
ans+=dp[S]*f[N-|S|];
#include<bits/stdc++.h>
using namespace std;
#define LL long long
using namespace std;
LL dp[1<<20+1],f[22]={1,1};
int x[25];
int main()
{
int N,n,m,i,j,p,k,t;
for(LL i=2;i<=20;++i) f[i]=f[i-1]*i;
cin>>t;
while(t--){memset(dp,0,sizeof(dp));dp[0]=1;
cin>>p>>n>>m;
N=n+m;
for(i=n+1;i<=N;++i) cin>>x[i];
for(i=0;i<(1<<N);++i){
if(!dp[i]) continue;
int a=0,b=0,c=0;
for(j=0;j<m;++j){
if(i&(1<<j)) {
c+=x[N-j];
++b;
}
}
if(c>=p) continue;
for(j=m;j<N;++j){
if(i&(1<<j)) a++;
}
if(a-b+1<1) continue;
for(j=0;j<N;++j){
if(i&(1<<j)) continue;
dp[i^(1<<j)]+=dp[i];
}
}LL xx=0,yy=f[N];
for(i=0;i<(1<<N);++i){
if(!dp[i]) continue;
int a=0,b=0,c=0,s=0;
for(j=0;j<N;++j) if(i&(1<<j)) s++;
for(j=0;j<m;++j){
if(i&(1<<j)) c+=x[N-j];
}
if(c<p) continue;
xx+=dp[i]*f[N-s];
}
LL tp=__gcd(xx,yy);
if(xx==0) yy=1;
else {xx/=tp;yy/=tp;}
printf("%lld/%lld
",xx,yy);
}
return 0;
}