求助简单期望dp

#include <iostream>
#include <cstring>
#include <queue>
#include <set>
#include <unordered_map>
#include <algorithm> 

using std::cin;
using std::cout;
using LL = long long;
using ld = long double;
using ull = unsigned long long;

ld f[110][1<<15]; // 期望最大得分
ld p[110][1<<15]; // 抵达某个状态的概率

int k,n;
int req[16],w[16]; // 宝物依赖（mask），得分

int main(){
	cin >> k >> n;
	for(int i=1,x;i<=n;i++){
		cin >> w[i] >> x;
		while(x) req[i] |= 1<<(x-1), cin >> x;
	}
	
	f[0][0]=0, p[0][0]=1;
	for(int i=0;i<k;i++){
		for(int S=0;S<(1<<n);S++){ // 前一个为S 向i转移
			for(int j=1;j<=n;j++){ // 转移时掉落了 j 物品
				if((req[j] & S) == req[j]){
					if(f[i][S]+w[j]*p[i][S] > f[i][S|(1<<(j-1))]){ // 比不选的朴素转移优，然后选；
						p[i+1][S|(1<<(j-1))]+=p[i][S]/n;
						f[i+1][S|(1<<(j-1))]+=(f[i][S]+w[j]*p[i][S])/n;
					}
					else p[i+1][S]+=p[i][S]/n, f[i+1][S]+=f[i][S]/n; // 没选；
				}
				else p[i+1][S]+=p[i][S]/n, f[i+1][S]+=f[i][S]/n; // 不能选；
			}
		}
	}
	ld ans=0;
	for(int S=0;S<(1<<n);S++) ans+=f[k][S];
	printf("%.6Lf",ans);
	return 0;
} 

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