2021.09 ccf csp 第四题 收集卡牌

思路

这题如果直接计算，因为不同的分类种数太多，枚举所有的分类情况是一个几乎不可能的复杂任务。

但不同摸牌次数，不同已摸出牌种类的子问题的答案之间，具有一定的递推关系。这种特征说明该问题可以使用动态规划来解决。

设$dp[i][j]$为动态规划状态，其中$i$表示已摸出牌种类的二进制，$i$从右数第$k$位表示第$k$种牌是否被摸到过，$j$表示摸到的牌总张数。设$cnt[i]$为当前摸到牌的种类数。

这样可以一次兑换到所有没摸到牌的条件是$(j-cnt[i])/k+cnt[i]==n$，去掉$cnt[i]$种已摸到的牌之后，剩下的$k$张换$1$张，恰好能换到所有没摸到的牌。

因为给定$dp[i][j]$，没有办法枚举每个$dp[i][j]$依赖的$dp$元素。所以只能用更新法，更新每个依赖$dp[i][j]$的$dp$元素。

代码

#include <bits/stdc++.h>

using namespace std;

int n, k;

double p[18];

double dp[(1 << 16) + 5][90];

int cnt[(1 << 16) + 5];

double ans;

int main() {

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    cin >> n >> k;

    for (int i = 0; i < n; ++i)

        cin >> p[i];

    int upper = 1 << n;

    for (int i = 1; i < upper; ++i) {

        int x = i;

        while (x)

            x &= x - 1, ++cnt[i];

    }

    dp[0][0] = 1.0;

    for (int i = 0; i < upper; ++i) {

        for (int j = 0; j < 90; ++j) {

            if ((j - cnt[i]) / k + cnt[i] == n) {

                ans += dp[i][j] * j;

                continue;

            }

            for (int m = 0; m < n; ++m) {

                if (i & (1 << m))

                    dp[i][j + 1] += dp[i][j] * p[m];

                else

                    dp[i | (1 << m)][j + 1] += dp[i][j] * p[m];

            }

        }

    }

    cout << fixed << setprecision(10) << ans << endl;

    return 0;

}

2021.09 ccf csp 第四题 收集卡牌的相关教程结束。