hdu 5816 Hearthstone(状态压缩dp)

题意：

牌堆里有 N张 A类卡，M张 B类卡
A类卡能让你从牌堆里抽两张卡
第 i张 B类卡能让你对对手造成 x_i点伤害
刚开始从牌堆抽 1张牌，并且对手有 P点生命值
问一回合内打倒对手的概率是多少

题解：

利用枚举子集的状态转移，求出手上能拿到牌的组合方案数。

 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int N=21;
 8 int t,p,n,m,a[N],U,A;
 9 ll dp[1<<20],fac[N]={1},ans;
10 
11 int check(int s)
12 {
13     int sum=0;
14     for(int i=n+m-1;i>=n;i--)
15         if(s&(1<<i))sum+=a[i-n+1];
16     if(sum>=p)return 1;
17     return 0;
18 }
19 
20 int main(){
21     F(i,1,N-1)fac[i]=fac[i-1]*i;
22     scanf("%d",&t);
23     while(t--)
24     {
25         scanf("%d%d%d",&p,&n,&m);
26         F(i,1,m)scanf("%d",a+i);
27         mst(dp,0),dp[0]=1,ans=0;
28         U=(1<<(n+m))-1,A=(1<<n)-1;
29         F(i,0,U)
30         {
31             if(!dp[i])continue;
32             int all=__builtin_popcount(i);
33             int haveA=__builtin_popcount(i&A);
34             if(check(i))
35             {
36                 ans+=dp[i]*fac[n+m-all];
37                 continue;
38             }
39             if(haveA*2+1<=all)continue;
40             F(j,0,n+m-1)if((i&(1<<j))==0)
41                 dp[i^(1<<j)]+=dp[i];
42         }
43         ll g=__gcd(ans,fac[n+m]);
44         printf("%lld/%lld
",ans/g,fac[n+m]/g);
45     }
46     return 0;
47 }

View Code