题解 P2473 [SCOI2008]奖励关

· · 题解

原题传送门：P2473 [SCOI2008]奖励关

题目简介：

共有 K 轮，有 n 种物品，每一轮出现每一种物品的概率是 \frac{1}{n} ，物品可选可不选，对于选每一种物品，必须要在前面的轮先选给定的部分物品，每一种物品的价格可正可负。求 K 轮后按最优方案选择的期望价格。

数据范围：1 \leq K \leq 100,1 \leq n \leq 15。

解题思路：

我们可以发现 n 的值很小，所以考虑使用状压DP，那么DP的式子是什么呢？

经过思考，我们基本上都可以推出，此轮的期望值=（上一轮所有可行状态的期望值+此轮所有对应可行状态的物品价格）的总和/总情况数。

再分情况讨论，设 dp_{i,j} 为第 i 轮状态为 j 的期望值（ j 是以二进制表示每个物品取或不取）， k 为第几种物品。

那么式子应为

dp_{i,j|(1<<(k-1))}=\sum max(dp_{i-1,j|(1<<(k-1)},dp_{i-1,j}+v_i)(j \& state_k==state_k)

否则dp_{i,j|(1<<(k-1))}= \sum dp_{i-1,j|(1<<(k-1)}

但是我们需要计算期望值，就是再除以总情况数，这个时候我们会发现有的情况在转移时是不存在的，总情况数是不定的，所以无法计算，而且任何状态都有可能是 K 轮后的状态，所以考虑从已知推未知，采用倒推，可以推出每一个可能的状态。

上面的式子修改后如下

dp_{i,j}= \sum max(dp_{i+1,j|(1<<(k-1)}+v_i,dp_{i+1,j})(j \& state_k==state_k)

否则dp_{i,j}= \sum dp_{i+1,j}

这样的话每一个状态转移后的 dp_{i,j} 的情况数都是 n ，除以 n 即可。

这样的话从 k 循环到 1 ，就可以理解为从所有状态转移到所有可行的 dp_{k,j} 再转移到所有可行的 dp_{k-1_j} ，最终状态就是 i 循环到 1 后，计算完后的 dp_{1,0} 就是第 0 轮还没有取时的状态，也就容纳了所有的可行状态。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int K,n,v[16],state[16];
double dp[105][1<<15];
inline double Max(register double a,register double b){
    return a>b?a:b;
}
int main(){
    scanf("%d%d",&K,&n);
    int tmp;
    for(int i=1;i<=n;++i){
        scanf("%d",&v[i]);
        while(~scanf("%d",&tmp)){
            if(!tmp)break;
            state[i]|=(1<<(tmp-1));
        }
    }
    for(int i=K;i>=1;--i){
        for(int j=0;j<(1<<n);++j){
            for(int k=1;k<=n;++k){
                if((j&state[k])==state[k])dp[i][j]+=Max(dp[i+1][j],dp[i+1][j|(1<<(k-1))]+v[k]);
                else dp[i][j]+=dp[i+1][j];
            }
            dp[i][j]/=n;
        }
    }
    printf("%.6lf",dp[1][0]);
    return 0;
}