题解 | #[SCOI2008]奖励关#

倒着推导

pre[]为预处理的满足条件的数组，k表示有k类物品

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

const int N = 16;

int n,k,score[N],pre[N];
double f[110][1<<N];
/*f[i][st]表示前i关状态为st的最大值*/
void solve(){
    for(int i = n ; i >= 1 ; i --){
        for(int st = 0; st <= (1 << k)-1 ; st ++){
            for(int j = 0 ; j< k; j ++){
                if((pre[j] & st) == pre[j])
                    f[i][st] += 1.0*max(f[i+1][st] , f[i+1][st|( 1 << j)] + score[j])/k;
                else
                    f[i][st] += 1.0*f[i+1][st]/k;
            }
        }
    }
    cout <<fixed << setprecision(6) << f[1][0] << endl;
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < k ; i++)
    {
        cin >> score[i];
        int p; cin >> p;
        while(p){
            pre[i] |= (1<<p-1);
            cin >> p;
        }
    }
    solve();
    return 0;
}