题意:传送门
题解:用dp[i][j]代表从第i个宝物开始,当前状态(已经取过的宝物)为j的情况下,用最优策略应对,到最后可以取得的分数的期望值。因为当前这一轮出现任何宝物的几率相等,所以期望值等于 所有情况下期望得分的和 除以 情况数。而出现第k种宝物的情况下,期望得分为max(dp[i+1][j],dp[i+1][j|1<<k] + P[k])。所以,转移方程为
dp[i][j]=Σ(1<=k<=N)max(dp[i+1][j],dp[i+1][j|1<<k] + P[k]) / N。
dp[i][j],i>N的情况是基础情形,期望得分为0。
那么,如何根据已有的结果,得到最优应对策略呢?假设当前正在出现第i个宝物,状态为j,出现了第k种宝物。如果状态j不满足要求,自然不收取宝物。否则,如果dp[i+1][j]>dp[i+1][j|1<<k]+P[k],则说明不收取的期望收益大,反之则是收取的期望收益大。
最后直接记忆化搜索即可。
附上代码:
第二种是使用倒推,因为正推对于dp[i][s],可能在第i轮到不了s这个状态,依然用dp[i][j]代表从第i个宝物开始,当前状态(已经取过的宝物)为j的情况下,用最优策略应对,到最后可以取得的分数的期望值。然后就能从后往前递推,如果对于第i种物品,能取的话,那么从取它和不取它导出最大值,如果不能取,直接加上后面的值即可,最后算期望,统一除以个数即可。
附上代码:
以上就是本篇文章【哪几个做内贸的网站比较好一点/厉害的seo顾问】的全部内容了,欢迎阅览 ! 文章地址:http://dh99988.xhstdz.com/xwnews/594.html
栏目首页
相关文章
动态
同类文章
热门文章
网站地图
返回首页 物流园资讯移动站 http://dh99988.xhstdz.com/mobile/ , 查看更多