收集卡牌 第23次CCF-CSP计算机软件能力认证

穷举序列法：通过两个序列点

记忆化搜索+状态压缩+dp

状态压缩：把状态state变成int类型每一位代表一个硬币
记忆化搜索  ；f[state][coins]这种状态之前有就直接返回
f[state][coins]表示当前状态下还需要抽卡次数的期望

可以由以下代码递推获得 dp函数的返回值代表当前dp状态的返回值。

总结就是使用dp[state][coins]来表示每一种状态 值代表当前状态下的期望

使用递归函数当到达终点使用r表示当前剩余需要的硬币数 返回0期望来进行dp递归

最后递归函数返回当前状态下的dp结果。

    v=0;
    for(int i=0;i<n;i++)//枚举这次抽到每种卡
    {
        if(state>>i&1)//这个卡有了
            v+=p[i]*(dp(state,coins+1,r)+1);//右边括号是下一种状态下需要抽卡的次数期望+1（这次抽的）
        else//这个卡没有
            v+=p[i]*(dp(state|1<<i,coins,r-1)+1);
    }

#include<bits/stdc++.h>
#include <algorithm>
#include<unordered_set>
using namespace std;
int n, k;
vector<double> pi(18, 0);
//穷举每一种情况
double result = 0;
//num:现在拥有的硬币数量 card:现在拥有的卡片 
//p：目前这种状态的概率 cot抽卡的次数
void dfs(unordered_set<int> card,int num,double p,int cot) {
    if ((card.size()+(num/k))>=n) {
        result += p * cot;
        return;
    }
    //遍历每一种卡片
    for (int i = 1; i <= n; i++) {
        if (card.find(i) == card.end()) {
            card.insert(i);
            dfs(card, num, p * pi[i], cot + 1);
            card.erase(i);
        }
        else {
            num++;
            dfs(card, num, p * pi[i], cot + 1);
            num--;
        }
    }
    return;
}
void work(){
    unordered_set<int> card;
    dfs(card,0,1,0);
    cout << fixed << setprecision(10)<< result;
}
int main() {
    //n：n种卡牌
    //k：k枚硬币可以换取一张卡牌
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> pi[i];
    }
    work();
    return 0;
}

//记忆化：如果v改变过就不要再搜了，防止一个搜很久的东西还要搜很多遍！！！
//为什么是dp：用f数组存了状态和硬币数对应期望，防止再次遍历
//期望题求法：sigma(概率*值)（注意，之前求出的期望可以作为值使用）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <iomanip>

using namespace std;

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

int n,m;
double p[N];
double f[M][5*N+1];//第一维：状态，第二维：硬币数；值：满足这两个状态，还需要的抽卡次数的期望

double dp(int state,int coins,int r)//状态，硬币数，还剩几种卡没得到；返回值：还需要的抽卡次数的期望
{
    auto& v=f[state][coins];//为了省代码而写，v是这个元素的同名，改变v就是改变这个元素
    if(v>=0)//这个状态和硬币数，之前求过期望
        return v;
    if(coins>=r*m)//已经可以买下剩下的所有卡片
    {
        v=0;
        return 0;
    }
    v=0;
    for(int i=0;i<n;i++)//枚举这次抽到每种卡
    {
        if(state>>i&1)//这个卡有了
            v+=p[i]*(dp(state,coins+1,r)+1);//右边括号是下一种状态下需要抽卡的次数期望+1（这次抽的）
        else//这个卡没有
            v+=p[i]*(dp(state|1<<i,coins,r-1)+1);
    }
    return v;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
        scanf("%lf",&p[i]);
    memset(f,-1,sizeof f);//为了记忆化搜索的初始化，如果求过的值，应该是正数
    cout<<fixed<<setprecision(10)<<dp(0,0,n)<<endl;
    return 0;
}