收集卡牌 第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;
}