收集卡牌（期望DP、状态压缩）

题意

小林在玩一个抽卡游戏，其中有\(n\)种不同的卡牌，编号为\(1\)到\(n\)。

每一次抽卡，她获得第\(i\)种卡牌的概率为\(p_i\)。

如果这张卡牌之前已经获得过了，就会转化为一枚硬币。

可以用\(k\)枚硬币交换一张没有获得过的卡。

小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。

如果你给出的答案与标准答案的绝对误差不超过\(10^{−4}\)，则视为正确。

提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。

题目链接：https://www.acwing.com/problem/content/4012/

数据范围

\(1 \leq n \leq 16\)
\(1 \leq k \leq 5\)
\(\sum\limits_{i=1}^n p_i = 1\)

思路

期望DP。首先我们分析一下状态定义。如果没有硬币这个设定，状态就是\(S\)，记录已经获得了哪些牌。现在加上硬币这个设定，那么我们再加一维状态，表示已经获得了多少金币。

定义\(f(S, j)\)表示当前卡牌获得情况为\(S\)，并且已经获得了\(j\)枚硬币的情况下，还需要抽卡次数的期望。

我们令\(r\)表示\(S\)的二进制表示中\(0\)的个数，因此终止状态为\(j \geq rk\)。

下面考虑转移方程。如果当前摸到的牌之前已经摸到过了，则\(f(S, j) = f(S, j) + p_i * (f(S, j + 1) + 1)\)；如果当前摸到的牌之前没有摸过，则\(f(S, j) = f(S, j) + p_i * (f(S | 2^i, j) + 1)\)。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 16, M = 1 << N;

int n, k;
double a[N];
double f[M][5 * N + 10];

double dfs(int state, int coins)
{
    double &v = f[state][coins];
    if(v >= 0) return v;
    int r = n;
    for(int i = 0; i < n; i ++) {
        if(state >> i & 1) {
            r --;
        }
    }
    if(coins >= r * k) return v = 0;
    v = 0;
    for(int i = 0; i < n; i ++) {
        if(state >> i & 1) v += a[i] * (dfs(state, coins + 1) + 1);
        else v += a[i] * (dfs(state | (1 << i), coins) + 1);
    }
    return v;
}

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