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 第四题收集卡牌

2021.09 ccf csp 第四题收集卡牌

思路

代码

最新文章

热门文章

巴特西

2021.09 ccf csp 第四题 收集卡牌

2021.09 ccf csp 第四题 收集卡牌

思路

代码

最新文章

热门文章

2021.09 ccf csp 第四题收集卡牌

2021.09 ccf csp 第四题收集卡牌