状态压缩DP
根据期望的线性性，我们知道可以分开考虑每个物品在每一时刻出现的期望
然后把这些期望加起来再除以物品种类数（因为要求平均期望，而每种物品出现的概率都是1/k）
那么DP方程就是
f[i][j]+=max(f[i+1][j],f[i+1][j|bit[k]]+score[k]);(其中满足可以取k物品的条件)
f[i][j]+=f[i+1][j];(当前枚举到的k物品没办法取到所得到的上一次的平均得分期望)
最后f[i][j]/=k就可以了
为什么要从f[i+1][j]推导f[i][j]?因为如果顺推的话有可能会枚举到无效的状态，而且最后没办法输出f[n][j]
所以只需要倒推就可以解决问题啦
#include<cstdio>
#include<algorithm>
using namespace std;
int k,n,bit[25],ist[25],score[25];
double f[105][1<<15];
int main(){
freopen("1076.in","r",stdin);
freopen("1076.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=20;i++)bit[i]=1<<(i-1);
for(int i=1;i<=k;i++){
scanf("%d",&score[i]);
int tp;
for(int j=0;scanf("%d",&tp),tp;j++){
ist[i]|=bit[tp];
}
}
for(int i=n;i>=1;i--){
for(int j=0;j<=bit[k+1]-1;j++){
for(int l=1;l<=k;l++){
if((j&ist[l])==ist[l]){
f[i][j]+=max(f[i+1][j],f[i+1][j|bit[l]]+score[l]);
}
else f[i][j]+=f[i+1][j];
}
f[i][j]/=k;
}
}
printf("%.6f\n",f[1][0]);
return 0;
}
评论 (0)
