題目大意
k 次機會，每次等概率隨機獲得 n 種寶物之一。寶物有前置依賴（吃過某些寶物才能吃）。求最優策略下的期望總得分。
狀態定義
f[i][mask]：第 i 次機會（從後往前推），當前已獲得寶物集合為 mask 時的最大期望得分。
轉移方程（逆序 DP）
for i = k .. 1:
for mask = 0 .. (1<
關鍵點
- 逆序 DP：從最後一步向前推，自然體現「最優策略」
- 狀態壓縮：n ≤ 15 ⇒ 狀態數 2¹⁵ = 32768
- 每步枚舉所有寶物，可吃則取 max(吃, 不吃)
- 答案為
f[1][0]
C++ 實現
#include <cstdio>
#include <cstring>
using namespace std;
double f[110][1<<15];
int score[20], pre[20];
int k, n;
int main() {
scanf("%d%d", &k, &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &score[i]);
for (int x; scanf("%d", &x) && x; )
pre[i] |= 1 << (x-1);
}
for (int i = k; i >= 1; --i)
for (int mask = 0; mask < (1<
複雜度
- 時間：O(k · n · 2ⁿ) ≈ 110 × 15 × 32768 ≈ 5.4×10⁷
- 空間：O(k · 2ⁿ) ≈ 110 × 32768 × 8B ≈ 28 MB
