又抄了一篇题解
要凉了要凉了，开学了我还什么都不会
文化课凉凉，NOIP还要面临爆零退役的历史进程
这道题挺神的，期望+状态压缩
我们设(dp[i][S])表示在第(i)天前，捡的宝物状态为(S)到第(K)天结束的期望收益是多少
于是我们的答案是(dp[1][0])，也就是第一天前（就是没开始）什么宝物也没有到结束的期望是多少
期望倒着推，我们的初始状态就是(dp[k+1]={0})
之后对于一个状态(dp[i][S])
在第(i)天(m)种宝物出现的概率都是(1/m)
所以枚举每一种宝物(j)，如果这个宝物的前提条件被(S)包含
就有
[dp[i][S]+=max(dp[i+1][S|(1<<(j-1))]+val[j],dp[i+1][S])*1/m
]
就是就算可以选择这个宝物的话，我们也两种选择拿或者不拿这个宝物
如过没有被包含，你只能不拿这个宝物
[dp[i][S]+=dp[i+1][S]*1/m
]
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#define re register
#define max(a,b) ((a)>(b)?(a):(b))
inline int read()
{
char c=getchar();
int x=0,r=1;
while(c<'0'||c>'9')
{
if(c=='-') r=-1;
c=getchar();
}
while(c>='0'&&c<='9')
x=(x<<3)+(x<<1)+c-48,c=getchar();
return x*r;
}
double dp[102][32769];
int n,m,N;
int cost[16];
int f[16];
int main()
{
n=read(),m=read();
for(re int i=1;i<=m;i++)
{
cost[i]=read();
int x=read(),y=0;
while(x) y|=1<<(x-1),x=read();
f[i]=y;
}
N=(1<<m)-1;
for(re int i=0;i<=N;i++) dp[n+1][i]=0;
for(re int i=n;i;i--)
for(re int j=0;j<=N;j++)
{
for(re int k=1;k<=m;k++)
if(((f[k]|j)==j))
{
dp[i][j]+=max(dp[i+1][j],dp[i+1][j|(1<<(k-1))]+cost[k])/double(m);
}else dp[i][j]+=dp[i+1][j]/double(m);
}
printf("%.6lf",dp[1][0]);
return 0;
}