P2473 [SCOI2008] 奖励关
题目大意
一个游戏有 n 个物品,在一个关卡中会等概率在其中掷出 k 个物品,但是每个物品都有前置 Si,只有收集了 Si 中的所有物品才能收集 ki,每个物品都有一个价值 pi,求获得金币的期望值。
数据范围:1≤n≤15,1≤k≤100,−106≤pi≤106。
题解
由于 n≤15,这提示我们使用状态压缩,考虑 f[i][S] 表示 i∼k 轮中,当前物品收集状态为 S 的期望金币数。
考虑转移,显然若 Si⊆S,则第 i 个物品可选也可不选,也就是 f[i+1][S] 或 f[i+1][S∪{i}]+pi。
考虑边界,显然 f[k+1][0]=0。
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef double DB;
const int N = 16 , M = 110;
int n , m;
int p[N];
int g[N];
DB f[M][1<<N];
int main() {
scanf("%d%d" , &m , &n);
for(int i = 1 ; i <= n ; i ++) {
scanf("%d" , &p[i]);
int x;
while(scanf("%d" , &x) , x != 0)
g[i] |= 1<<(x-1);
}
for(int i = m ; i >= 1 ; i --) {
for(int state = 0 ; state < (1<<n) ; state ++) {
for(int j = 1 ; j <= n ; j ++) {
if((state & g[j]) == g[j]) {
f[i][state] += max(f[i+1][state] , f[i+1][state|(1<<(j-1))]+p[j]);
} else {
f[i][state] += f[i+1][state];
}
}
f[i][state] /= n;
}
}
printf("%.6lf\n" , f[1][0]);
return 0;
}