HDU 5816 Hearthstone

做过类似感觉的题，但是就是没办法往状压上靠，找不到之间的联系。

题意：给你一个p，n张无中生有，m张伤害牌。抽一张牌，问杀死他的概率是多大。

20张牌直接存状态，往下转移的时候如果叶子数大于等于无中生有数加一就是边界，不能更新了。因为想象一颗满二叉树，伤害牌就是叶子，无中生有就是里面的。正好对应了这道题的摸牌过程。

把一种答案考虑成一种序列，这种开头的序列已经必赢了，那后面怎么排是牌的自由，最后除以总排列数就OK了。

网上这两个地方说的不太明确，这是我的理解。

#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> #include <iostream> #include <cstdlib> #include <string> #include <vector> #include <set>using namespace std; typedef long long LL; LL fac[22]; LL val[22]; LL dp[1<<21]; int main() {fac[1]=fac[0]=1;for (LL i=2;i<=20;i++)fac[i]=fac[i-1]*i;int T;scanf ("%d",&T);while (T--){memset(dp,0,sizeof(dp));LL p,n,m;scanf ("%I64d%I64d%I64d",&p,&n,&m);LL N=n+m;for (LL i=n;i<N;i++)scanf ("%I64d",&val[i]);dp[0]=1;for (LL st=0;st<(1<<N);st++){if (dp[st]==0) continue;LL dam=0,num_a=0,num_b=0;for (LL i=n;i<N;i++){if (st&(1<<i)) dam+=val[i],num_b++;}if (dam>=p) continue;for (LL i=0;i<n;i++){if (st&(1<<i)) num_a++;}if (num_a+1<=num_b) continue;for (LL i=0;i<N;i++){if (st&(1<<i)) continue;dp[st+(1<<i)]+=dp[st];}}LL ans=0,all=fac[N];for (LL st=0;st<(1<<N);st++){if (dp[st]==0) continue;LL dam=0,num=0;for (LL i=n;i<N;i++){if (st&(1<<i)) dam+=val[i],num++;}for (LL i=0;i<n;i++){if (st&(1<<i)) num++;}if (dam>=p){ // cout<<dp[st]<<" "<<st<<" "<<fac[N-num]<<endl;ans+=dp[st]*fac[N-num];}}LL e=__gcd(ans,all);printf ("%I64d/%I64d\n",ans/e,all/e);}return 0; }

 

转载于:https://www.cnblogs.com/nj-czy/p/5765450.html

总结

以上是生活随笔为你收集整理的HDU 5816 Hearthstone的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。