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;
}
      

那麼今天就講到這裡了，我們下期再見~