题解与代码 - 奖励关

奖励关

状压动态规划

从数据范围容易猜到本题应该用状压 dp。

记 $dp_{i,j}$ 表示已经到了第 $i$ 次抛出宝物，已经吃过的宝物的集合为 $j$ 。易知

$dp_{i,j}=\frac 1n\cdot\sum_{k=1}^n\begin{cases} \max\{dp[i + 1][j],dp[i + 1][j|1<<(k-1)]+p_k\}, & \text{if can get item }k \\ dp[i + 1][j], & \text{if cannot get item }k \end{cases}.$

代码

// 2023.05.24

#include<bits/stdc++.h>
using namespace std;

int n,k,p[16],r[16];
double dp[102][1<<15];

int main(){
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",p+i);
        int x; scanf("%d",&x);
        while(x)
            r[i]|=1<<x-1,
            scanf("%d",&x);
    }
    for(int i=k;i>=1;i--)
        for(int j=0;j<(1<<n);j++){
            for(int t=1;t<=n;t++)
                if((j|r[t])==j)
                    dp[i][j]+=max(dp[i+1][j|(1<<(t-1))]+p[t],dp[i+1][j]);
                else dp[i][j]+=dp[i+1][j];
            dp[i][j]/=n;
        }
    printf("%.6lf\n",dp[1][0]);
    return 0;
}