This page looks best with JavaScript enabled

「SCOI2008」奖励关-期望dp

 ·  ✏️ About  422 words  ·  ☕ 1 mins read · 👀... views

系统将依次随机抛出 $k$ 次宝物,每次你都可以选择吃或者不吃。宝物一共有 $n$ 种,系统每次抛出这 $n$ 种宝物的概率都相同且相互独立。

吃一次第 $i$ 种宝物将得到 $P_i$ 分,但并不是每种宝物都是可以随意获取的。第 $i$ 种宝物有一个前提宝物集合 $S_i$ 。只有当 $S_i$ 中所有宝物都至少吃过一次,才能吃第 $i$ 种宝物。注意,$P_i$ 可以是负数。

假设你采取最优策略,平均情况你一共能在奖励关得到多少分值?

链接

Luogu P2473

题解

为了方便最后答案的计算,我们设 $dp[i][S]$ 为当前已经吃了 $i$ 次,并且已经吃到的宝物的集合为 $S$ ,到最后(吃完 $k$ 次)能够获得。

然后状态转移( $W_i$ 为单独取 $i$ 的集合):

$$
dp[i][S] = \frac{1}{n}\sum_{i = 1}^{n}
\begin{cases}
min(dp[i+1][S],dp[i+1][S \cup W_i] + P_i),S_i \subset S\
dp[i+1][S],S_i \not\subset S
\end{cases}
$$

状压,转移即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 110;

int k,n;
int q[MAXN],p[MAXN],t;

double dp[MAXN][1<<16];//1<<type代表第i种

void init(){
    scanf("%d %d",&k,&n);
    for(int i = 1;i<=n;i++){
        scanf("%d %d",&p[i],&t);
        while(t!=0)
            q[i] |= (1<<(t-1)),scanf("%d",&t);
    }
}

void solve(){
    for(int i = k-1;i>=0;i--){
        for(int j = 0;j<=(1<<n)-1;j++){
            for(int w = 1;w<=n;w++)
                dp[i][j] += max(dp[i+1][j],(q[w]&j)==q[w]?dp[i+1][j|(1<<w-1)]+p[w]:-1e9);
            dp[i][j]/=n;
        }
    }
    printf("%.6lf\n",dp[0][0]);
}

int main(){
    init();
    solve();
    return 0;
}

cqqqwq
WRITTEN BY
cqqqwq
A student in Computer Science.

评论: