hdu_5816 Hearthstone

Contents

题目：

Hearthstone is an online collectible card game from Blizzard Entertainment. Strategies and luck are the most important factors in this game. When you suffer a desperate situation and your only hope depends on the top of the card deck, and you draw the only card to solve this dilemma. We call this "Shen Chou Gou" in Chinese.
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.

思路：

根据概率的定义，胜利的概率等于胜利的情况除以总的情况数，所以只要求出胜利的情况数即可。
因为最大只有二十，所以可以状压保存取了的牌的情况，枚举所有的情况即可。
所以要判断哪些情况是合法的，设为A卡个数，为B卡个数。当<时当前状态不合法，当时，当前状态没有后继状态。
设代表状态为时的情况种数，如果状态可以打死对方，那么胜利的情况数就是为剩余卡数。
转移就直接枚举每一张牌就好啦。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
ll fac={1},dp[(1<<20)+5];
int x;
int main(){
for(int i=1;i<=20;i++)
fac[i]=fac[i-1]*i;
int T,n,m,p;
scanf("%d",&T);
while(T--){
ll ans=0;
scanf("%d%d%d",&p,&n,&m);
for(int i=0;i<m;i++)
scanf("%d",x+i);
memset(dp,0,sizeof(dp));
dp=1;
for(int bin=0;bin<(1<<n+m);bin++){
if(!dp[bin])continue;
int A=0,B=0,D=0;
for(int i=0;i<n;i++)
if((bin>>i)&1)
A++;
for(int j=0;j<m;j++)
if((bin>>(j+n))&1){
B++;
D+=x[j];
}
if(A-B+1<0)continue;
if(D>=p){
ans+=dp[bin]*fac[n+m-A-B];
continue;
}
if(A-B+1==0)continue;
for(int i=0;i<n+m;i++)
if(((bin>>i)&1)==0)
dp[bin|(1<<i)]+=dp[bin];
}
ll all=fac[n+m],g=gcd(all,ans);
printf("%lld/%lld\n",ans/g,all/g);
}
return 0;
}