HDU 5816 Hearthstone - dblank

HDU 5816 Hearthstone

传送门:HDU 5816 Hearthstone

思路:我们可以用状态压缩来表示当前抽排的状态。我们用ones数组来表示i的中含1的个数,也就是总共抽牌的个数,对于抽到的A类牌,我们还可以再抽ones[i] - 2res + 1。res是抽到的B类牌的牌数。对于一个已经获得的集合,我们可以统计B类牌的伤害和是否可以可以斩杀对方。如果可以的话,此时的方案数就是dp[i]fact[m+n-ones[i]]。用dp[i]表示到达集合i的方案数。总的方案数就是fact[m+n]。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 100000 + 10, Mod = 110119;
typedef long long  ll;
ll fact[22], dp[(1LL<<20)+10];
int ones[(1LL<<20)+10], a[22], p, n, m;
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a%b);
}
void init()
{
    int sz = 1LL<<20;
    fact[0] = 1;
    for(int i = 1; i<=20; i++)
        fact[i] = fact[i-1] * i;
    for(int i = 0; i<sz; i++)
    {
        for(int j = 0; j<20; j++)
        {
            if(i & 1<<j)
                ones[i] ++;
        }
    }
}
int judge(int sta)
{
    int res = 0;
    for(int i = 0; i<m; i++)
    {
        if(sta & 1<<i)
            res += a[i];
    }
    return res;
}
bool can(int sta)
{
    int res = 0;
    for(int i = 0; i<m; i++)
        res += (bool)(sta & (1<<i));
    return ones[sta] - res*2+1;
}
int main()
{
    int t;
    init();
    cin>>t;
    while(t--)
    {
        scanf("%d%d%d", &p, &n, &m);
        for(int i = 0; i<m; i++)
            scanf("%d", &a[i]);
        int sz = (1<<(m+n))-1;
        ll ans = 0;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        if(judge(sz)>=p)
        {
            for(int i = 0; i<=sz; i++)
            {
                if(dp[i])
                    if(judge(i)>=p)
                        ans += dp[i]*fact[m+n-ones[i]];
                    else if(can(i)>0)
                    {
                        for(int j = 0; j<m+n; j++)
                        {
                            if(!(i & 1<<j))
                            {
                                dp[i | 1<<j] += dp[i];
                            }
                        }
                    }
            }
        }
        if(ans == 0)
            printf("0/1\n");
        else
        {
            ll g = gcd(ans, fact[n+m]);
            printf("%I64d/%I64d\n", ans/g, fact[m+n]/g);
        }
    }
    return 0;
}

相关文章

发表新评论