N 種卡片（N ≤ 20），每包零食隨機含一張卡片，第 i 種概率 p_i，也可能無卡片（∑p_i ≤ 1）。求集齊所有 N 種卡片的期望購買包數。
dp[mask] 表示已擁有卡片集合為 mask 時，還需要購買的期望包數。目標求 dp[0]。
轉移：從 mask 買一包，
p0 = 1 - ∑p_i 什麼也沒有，狀態不變，期望增加 1。p_i 得到卡片 i：
mask & (1<），狀態不變。 mask | (1<。 方程：
dp[mask] = 1 + p0·dp[mask] + Σ_{i∈mask} p_i·dp[mask] + Σ_{i∉mask} p_i·dp[mask|(1<移項整理：
dp[mask] = (1 + Σ_{i∉mask} p_i·dp[mask|(1<#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
double p[22], dp[1<<20];
int n;
double solve(int mask) {
if (mask == (1< 0) return dp[mask];
double sum_p = 0, exp = 1;
for (int i = 0; i < n; ++i) {
if (mask & (1<
關鍵點解析
- 分母意義：
sum_p 是「獲得新卡片」的總概率。若 sum_p == 0（已集齊或剩餘卡片概率為 0），基本情況返回 0。
- 遞歸順序：從全集向空集遞歸，或按
mask 從大到小迭代 DP 均可。遞歸 + 記憶化代碼最簡潔。
- 精度：
double 足夠，輸出 %.3f 或 %.4f 滿足 1e-4 要求。
- 狀態數：
2^20 = 1,048,576，邊界情況需優化內存（可用 float 或壓縮），但 N≤20 通常 N≤16 實際測試，double dp[1<<20] 約 8MB 可接受。
複雜度
- 時間：O(N·2^N)，N=20 時 ≈ 20M 操作，C++ 1s 內通過。
- 空間：O(2^N)。
總結
HDU 4336 是「收集期望 + 狀態壓縮 DP」的教科書級題目。核心在於建立期望方程並化簡，分母正是「有效轉移概率」，避免了無效自環的無限級數求和。狀態壓縮將集合狀態映射為整數，配合記憶化搜索或迭代 DP 高效求解。掌握此模板，可解決所有「隨機收集/轉移期望」類問題。
