P2473

· · 个人记录

[SCOI2008] 奖励关

顺推转移存在不确定状态是否存在的问题，并不好做。

于是想到逆推。

定义 f(i,q) 表示第 1 到 (i-1) 轮取过的宝物合集为 q，第 i 到 k 轮的最大期望得分。

那么若对于状态 q，第 j 个物品的前提为 c_j，当 c_j\subsetneq q 时，即 q\& c_j=c_j 的时候，我们可以选择转移或保留，即：

n\cdot f(i,q)=\max\{f(i+1,q),f(i+1,q|(1<<(j-1)))+p_j\}

反之，则必须要保留：

n\cdot f(i,q)=f(i+1,q)

最后答案即为 f(1,0)。

这里运用了一下滚动数组，但实际上每次还要赋初值，从常数的角度来说并不优，不如直接开大数组。

时间复杂度 O(kn\cdot 2^n)。

代码：

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=17;

ll n,k,x;

ll c[N+5];

double f[2][1<<N],p[N+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

int main() {

    k=read();n=read();

    for(ll i=1;i<=n;i++) {
        scanf("%lf",&p[i]);
        x=read();
        while(x>0) {
            c[i]|=(1<<(x-1));x=read();
        }
    }

    for(ll i=k;i>=1;i--) {
        for(ll j=0;j<(1<<n);j++) f[i&1][j]=0;
        for(ll q=0;q<(1<<n);q++) {
            for(ll j=1;j<=n;j++) if((q&c[j])==c[j]) {
                f[i&1][q]+=max(f[1^(i&1)][q|(1<<(j-1))]+p[j],f[1^(i&1)][q]);
            }
            else {
                f[i&1][q]+=f[1^(i&1)][q];
            }
            f[i&1][q]=f[i&1][q]/(double)n;
        }
    }

    printf("%.6f",f[1][0]);

    return 0;
}