【문제풀이】LuoGu2473: 보상 관문

#include 
#define maxn 110
#define maxm 100010
using namespace std;
double dp[maxn][maxm];
int n, m, power[maxn], a[maxn], p[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

int main(){
	m = read(), n = read();
	power[0] = 1;
	for (int i = 1; i <= n; ++i) power[i] = power[i - 1] << 1;
	for (int i = 1; i <= n; ++i){
		p[i] = read();
		int x = read();
		while (x) a[i] |= power[x - 1], x = read();
	}
	for (int i = m; i; --i)
		for (int j = 0; j < power[n]; ++j){
			for (int k = 1; k <= n; ++k)
				if ((j & a[k]) == a[k]) dp[i][j] += max(dp[i + 1][j], dp[i + 1][j | power[k - 1]] + p[k]);
				else dp[i][j] += dp[i + 1][j];
			dp[i][j] /= n;
		}
	printf("%.6lf
", dp[1][0]);
	return 0;
}