收集卡牌

算法笔记
, ,

收集卡牌

题目链接

原先我的思路是爆搜，可以拿到10分…

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
#include <bits/stdc++.h>
using namespace std;
int n, k;
double p[17];
bool has[17];
int coin_num;
double res;
void dfs(double prob, int has_card_num, int has_coin_num, int try_num) {
    if(has_card_num + has_coin_num / k >= n) {
        res += prob * try_num;
        return;
    }
    for(int i = 1; i <= n; ++i) {
        if(has[i]) {
            dfs(prob * p[i], has_card_num, has_coin_num+1, try_num+1);
        } else {
            has[i] = true;
            dfs(prob * p[i], has_card_num + 1, has_coin_num, try_num + 1);
            has[i] = false;
        }
    }
    return ;
}

int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    dfs(1,0,0,0);
    printf("%.6lf", res);
    return 0;
}

但是这样会有非常多冗余的搜索…同时，我们想到当dfs超时时一般会使用dp算法进行优化。同时，在题干中也提到了最多有16种卡牌，而$2^{16}$这个级别完全可以使用状压dp。

对于此类问题，我们可以先看一下绿豆蛙的归宿，作为解题的基本思路和基本模板来处理。虽然用的是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
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 200020;
int n, m, idx;
int h[M], e[M], ne[M], w[M], cnt[M];
double f[N]; // 最多经过N个点
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

double dp(int x) {
    if(f[x] >= 0) // 说明已经计算过了
        return f[x];
    f[x] = 0;
    for(int k = h[x]; k != -1; k = ne[k]) {
        // E(p(w + X)) = pw + pE(X)
        f[x] += (w[k] + dp(e[k])) / cnt[x];
    }
    return f[x];
}

int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i = 0; i < m; ++i) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        cnt[a]++;
    }
    memset(f, -1, sizeof f);
    printf("%.2lf", dp(1));
    return 0;
}

上面使用的是一种倒推的思想，依照上面的求解方式，对于解决这类问题应该更加容易去理解。

对于有关期望问题的求解，一般都会使用这样的形式，首先将所有的状态置为nan(memset double)，再递归进行求解。

下面给出dp算法的求解思路：

设二维数组f[i][j]，一维表示16种卡牌的拥有情况，第二维表示硬币数，二维数组的值为期望值。当当前拥有的卡牌种类数达标，或者加上硬币的数量达标之后，就应该增加期望值。

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
#include <bits/stdc++.h>
using namespace std;
int n, k;
double p[17];
double f[1<<16][81];
double dp(int card, int coin_num, int select_num, int card_num) {
    if(f[card][coin_num] >= 0) return f[card][coin_num];
    if(card_num + coin_num / k >= n) return select_num;
    f[card][coin_num] = 0;
    for(int i = 1; i <= n; ++i) {
        if((card >> (i-1)) & 1) {
            f[card][coin_num] += p[i] * dp(card, coin_num + 1, select_num+1, card_num);
        } else {
            f[card][coin_num] += p[i] * dp(card | (1 << (i-1)), coin_num, select_num+1, card_num + 1);
        }
    }
    return f[card][coin_num];
}

int main() {
    memset(f, -1, sizeof f);
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%lf", &p[i]);
    printf("%.10lf", dp(0, 0, 0, 0));
    return 0;
}

对于f[i][j]的定义应该进行进一步说明，它代表的是当前卡牌的拥有情况i以及硬币拥有情况数j情况下所有情况的期望抽取结果（假设当前的概率为1）。当已经有集齐所有卡牌时，显然其期望是从最初抽取卡牌的次数。如果还没能集齐所有卡牌，那么就需要思考每种卡牌抽取的概率，将所有子期望相加。该做法也是基于基础的期望表达式：
$$
E(X)=E(p_1X_1+p_2X_2+p_3X_3+…)=p_1E(X_1)+p_2E(X_2)+p_3E(X_3)
$$
初看的确有些难理解，希望能通过这题对期望的计算有更深刻的认识。