HDU 5816 Hearthstone【概率dp】

ACM_概率

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5816

题意：

有$n$张奥术智慧，$m$张火球术，给定每张牌会造成的伤害数以及对手的HP数，求杀死对手的概率是多少。

分析：

直接搜的话，会爆内存，要动态分配内存。
或者将问题转化为求$可以赢的抽牌的排列数/总排列数$。
用$dp$保存卡片对应状态的排列方案数，可能会面对三种情况。

  1. 无法再取牌
  2. 已经确定可以胜利
  3. 当前无法胜利但是可以继续取牌

第一种情况，计算可得此时$2*tA-(tA+tB)+1\ge0 $即$tA-tB+1\ge0$
第二种情况，直接将后面的所有排列数乘上当前$dp值$加到答案去即可。
第三种情况，枚举转移，继续计算。

代码：

记忆化搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*************************************************************************
    > File Name: 7.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/9 14:02:54
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1 << 20, maxm = 20 + 5;
typedef long long ll;
typedef pair<ll, ll>P;
int b[maxm];
vector<bool>vis;
vector<P>dp;
int HP, n, m;
ll gcd(ll a, ll b)
{
    return b?gcd(b, a % b): a;
}
//剩余牌、手上牌
int cal(int state)
{
    int ans = 0;
    while(state){
        if(state & 1) ans++;
        state >>= 1;
    }
    return ans;
}
P add(P x, P y)
{
    if(x.first == 0 && x.second == 0) x.second = 1;
    if(y.first == 0 && y.second == 0) y.second = 1;
    ll up = x.first * y.second + y.first * x.second;
    ll down = x.second * y.second;
    //cout<<"add"<<up<<" "<<down<<endl;
    ll g = gcd(up, down);
    return P(up / g, down / g);
}
P mul(P x, P y)
{
    if(x.first == 0 && x.second == 0) x.second = 1;
    if(y.first == 0 && y.second == 0) y.second = 1;
    ll up = x.first * y.first;
    ll down = x.second * y.second;
    ll g = gcd(up, down);
    return P(up / g, down / g);
}
P gao(int now, int val, int totn, int tot)
{
    if(val >= HP) return P(1, 1);
    if(vis[(now + 1) * (n + 1) + totn]) return dp[(now + 1) * (n + 1) + totn];
    vis[(now + 1) * (n + 1) + totn] = true;
    if(tot == 0) return P(0, 1);
    int totm = cal(now);
    if(totn > 0) dp[(now + 1) * (n + 1) + totn] = mul(gao(now, val, totn - 1, tot + 1), P(totn, totm + totn));
    else dp[(now + 1) * (n + 1) + totn] = P(0, 1);
    for(int i = 0; i < m; i++){
        if((now >> i) & 1){
            P tmp = gao(now ^ (1 << i), val + b[i], totn, tot - 1) ;
            tmp = mul(tmp, P(1, totm + totn));
            dp[(now + 1) * (n + 1) + totn] = add(dp[(now + 1) * (n + 1) + totn], tmp);
        }
    }
    return dp[(now + 1) * (n + 1) + totn];
}
int main (void)
{
    int T;scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &HP, &n, &m);
        for(int i = 0; i < m; i++) scanf("%d", &b[i]);
        vis.resize((1 << m) * (n + 1) + n + 1);
        vis.clear();
        dp.resize((1 << m) * (n + 1) + n + 1);
        dp.clear();
        P ans = gao((1 << m) - 1, 0, n, 1);
        printf("%lld/%lld\n", ans.first, ans.second);
    }
    return 0;
}

方法二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*************************************************************************
    > File Name: 7.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/9 14:02:54
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 1 << 20, maxm = 20 + 1;
typedef long long ll;
typedef pair<ll, ll>P;
int b[maxm];
ll dp[maxn];
ll fact[maxm];
int HP, n, m;
ll gcd(ll a, ll b)
{
	return b?gcd(b, a % b): a;
}
void init()
{
	fact[0] = 1;
	for(int i = 1; i < maxm; i++){
		fact[i] = fact[i - 1] * i;
	}
}
int calt(int i)
{
	int ans = 0;
	for(int j = 0; j < m; j++){
		if((i >> j) & 1) ans += b[j]; 
	}
	return ans;
}
int main (void)
{
	init();
	int T;scanf("%d", &T);
	while(T--){
		scanf("%d%d%d", &HP, &n, &m);
		for(int i = 0; i < m; i++) scanf("%d", &b[i]);
		memset(dp, 0, sizeof(dp));
		for(int i = 0; i < (n + m); i++) dp[1 << i] = 1;
		int A, B;
		int tA, tB;
		ll ans = 0;
		for(int i = 0; i < (1 << (n + m)); i++){
			if(dp[i] == 0) continue;
			B = i & ((1 << m) - 1);
			A = i >> m;
			tA = __builtin_popcount(A); tB = __builtin_popcount(B);
			if(calt(B) >= HP){
				ans += dp[i] * fact[n + m - tA - tB];
				continue;
			}
			if(tA - tB + 1 <= 0) continue;
			for(int j = 0; j < (n + m); j++){
				if(!((i >> j) & 1)){
					dp[i |(1 << j)] += dp[i];
				}
			}
		}
		ll g = gcd(ans, fact[n + m]);
		printf("%lld/%lld\n", ans / g, fact[m + n] / g);
	}
	return 0;
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析：
  4. 4. 代码：