CSP202109-4 收集卡牌 题解

好题，虽然看着像期望DP，但是装压好写。

〇、题目

题目描述

小林在玩一个抽卡游戏，其中有 \(n\) 种不同的卡牌，编号为 \(1\) 到 \(n\)。每一次抽卡，她获得第 \(i\) 种卡牌的概率为 \(p_i\)。如果这张卡牌之前已经获得过了，就会转化为一枚硬币。可以用 \(k\) 枚硬币交换一张没有获得过的卡。

小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过 \(10^{-4}\)，则视为正确。

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

输入格式

从标准输入读入数据。

输入共两行。第一行包含两个用空格分隔的正整数 \(n,k\)，第二行给出 \(p_1,p_2,...,p_n\)，用空格分隔。

输出格式

输出到标准输出。

输出共一行，一个实数，即期望抽卡次数。

样例1输入

2 2
0.4 0.6
      

样例1输出

2.52
      

样例1解释

共有 \(2\) 种卡牌，不妨记为 A 和 B，获得概率分别为 \(0.4\) 和 \(0.6\)，\(2\) 枚硬币可以换一张卡牌。下面给出各种可能出现的情况：

• 第一次抽卡获得 A，第二次抽卡获得 B，抽卡结束，概率为 \(0.4\times0.6=0.24\)，抽卡次数为 \(2\)。
• 第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 B，抽卡结束，概率为 \(0.4\times0.4\times0.6=0.096\)，抽卡次数为 \(3\)。
• 第一次抽卡获得 A，第二次抽卡获得 A，第三次抽卡获得 A，用硬币兑换 B，抽卡结束，概率为 \(0.4\times0.4\times0.4=0.064\)，抽卡次数为 \(3\)。
• 第一次抽卡获得 B，第二次抽卡获得 A，抽卡结束，概率为 \(0.6\times0.4=0.24\)，抽卡次数为 \(2\)。
• 第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 A，抽卡结束，概率为 \(0.6\times0.6\times0.4\)，抽卡次数为 \(3\)。

• 第一次抽卡获得 B，第二次抽卡获得 B，第三次抽卡获得 B，用硬币兑换 A，抽卡结束，概率为 \(0.6\times0.6\times0.6=0.216\)，抽卡次数为 \(3\)。

  因此答案是 \(0.24\times2+0.096\times3+0.064\times3+0.24\times2+0.144\times3＋0.216\times3=2.52\)。

样例2输入

4 3
0.006 0.1 0.2 0.694
      

样例2输出

7.3229920752
      

子任务

对于 \(20\%\) 的数据，保证 \(1\leq n,k\leq 5\)。

对于另外 \(20\%\) 的数据，保证所有 \(p_i\) 是相等的。

对于 \(100\%\) 的数据，保证 \(1\leq n\leq16,1\leq k\leq5\)，所有的 \(p_i\) 满足 \(p_i\geq \frac{1}{1000}\) ，且 \(\sum\limits_{i=1}^np_i=1\)。

一、思路

既然是选或者不选，那就推荐装压DP。

首先定义状态：\(f_{i,j}\)表示状态为\(i\)(二进制，表示抽到或者没有抽到)，已经抽了\(j\)次的概率。

边界条件肯定是\(f_{0,0}=1\)，没有抽的概率显然是\(100\%\)。

之后是状态转移方程。想要算f，就肯定需要循环枚举，我们跟着代码一起对照。

for(int i=0;i<=(1<<n);i++){//枚举状态
  for(int j=0;j<=100;j++){//枚举j，一定要设的大一点
    //如果已经有了x张卡牌，而且抽到的j张减去x张，也就是重复的张数再除以k（就是可以得到多少其他卡牌），再加上x是n，说明可以一次兑换，就抽了j次，概率dp[i][j]。
    if(cnt[i]+(j-cnt[i])/k==n){
      ans+=j*dp[i][j];//期望
      continue;//既然抽完了，就不需要再计算了
    }
    for(int k=1;k<=n;k++){//枚举抽到了哪一张卡牌
      if(i&(1<<(k-1))) dp[i][j+1]+=dp[i][j]*p[k];//出现过，状态不改变
      else dp[i+(1<<(k-1))][j+1]+=dp[i][j]*p[k];//状态改变
    }
  }
}
      

不过，我们要算的x不可能现场算，就必须预处理，叫做cnt。

预处理方式：

for(int i=1;i<=(1<<n);i++){//检查每一个状态
  x=i;//会变化
  while(x) x&=x-1,cnt[i]++;//二进制里一的个数就是答案
}
      

二、代码

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=(1<<17)+17;//防越界
double dp[maxn][100];
double p[100];
int cnt[maxn];
int main(){
  double ans=0;
  int n,k,x;
  cin>>n>>k;//输入
  for(int i=1;i<=n;i++) cin>>p[i];
  for(int i=1;i<=(1<<n);i++){//预处理
    x=i;
    while(x) x&=x-1,cnt[i]++;
  }
  dp[0][0]=1;
  for(int i=0;i<=(1<<n);i++){//计算
    for(int j=0;j<=100;j++){
      if(cnt[i]+(j-cnt[i])/k==n){
        ans+=j*dp[i][j];
        continue;
      }
      for(int k=1;k<=n;k++){
        if(i&(1<<(k-1))) dp[i][j+1]+=dp[i][j]*p[k];
        else dp[i+(1<<(k-1))][j+1]+=dp[i][j]*p[k];
      }
    }
  }
  printf("%.5lf",ans);//注意输出时要保留5位（好像6位更保险，5位过不了官方数据）
  return 0;
}
      

那么今天就讲到这里了，我们下期再见~