当前位置: 首页 > news >正文

可行性背包转方案数背包小技巧

在某些题目中,我们需要一个可行性背包,并且需要支持删除某个物品,这个时候我们就可以用到可行性转方案数背包的小技巧。

说人话,这个转换就是把 \(\text{bool}\) 类型的背包转换成 \(\text{int}\) 类型的方案数背包,这样做有什么用呢?

首先 \(\text{bool}\) 类型的 DP 显然是不支持删除的,如果每次都重新 DP 一次,单次复杂度是 \(O(nV)\) 的,太慢了。

那么转换成方案数背包我们就会有一个容斥的做法,具体来说,设我们要删除的物品大小为 \(w\),删除前的背包为 \(g_i\),删除后的背包为 \(f_i\),我们可以预处理出 \(g_i\),再利用 \(g_i\) 求出 \(f_i\),我们可以分类讨论得出这个转移:

\[f_i= \left\{ \begin{aligned} & g_i &,0 \le i < w\\ & g_i-f_{i-w} &,w \le i \le n \end{aligned} \right. \]

解释一下 \(f_{i-w}\) 的含义:\(i-w\) 的容量中不选 \(w\),剩下的容量选了一个 \(w\),所以指示了 \(g_i\) 中选了 \(w\) 的部分,正是我们需要减掉的部分。单次删除复杂度为 \(O(V)\)

http://www.sczhlp.com/news/80097/

相关文章:

  • 网站有哪些类型清河网站建设价格
  • 免费asp网站空间房价下跌最新消息
  • 襄阳做网站的公司有哪些电子商务平台的开发建设
  • 网站开发英语翻译黑龙江建设局网站
  • 公司宣传网站建设商业网站制作
  • 自己免费网站建设计算机软件网站建设
  • 企业网站建设中存在的问题分析备案期间怎么关闭网站
  • 企业网站pc优化网页建站费用
  • 微信公众号的步骤界首网站优化公司
  • 网站开发费走什么科目重庆市门户网站制作
  • 做门户网站的营业范围营销策划与运营公司
  • 济南一哥网站建设郑州妇科医院正规有哪些
  • 赚钱的网站做任务济南突然宣布
  • 潍坊专职消防员待遇成都正规搜索引擎优化
  • 服装商城的网站建设网站怎么做图片动态图片不显示了
  • 深圳推广系统哪家好页面优化的方法有哪些
  • 英语_阅读_A Drop of Hope in a Thirsty World_待读
  • 营销型网站设计价格网站建设教程主页
  • 个人设计网站论文摘要专门做推荐的网站
  • 宁波网站搜索排名哈尔滨网站建设培训班
  • 网站开发外包计入什么科目桐乡 网站建设
  • C# Avalonia 13- MoreDrawing - Drawings
  • 添加书签网站代码北京建网
  • 如何提升wordpress网站速度淘宝店标在线制作免费
  • 优化算法 网站网站优化公司收费
  • 餐饮网站开发背景苏州吴中区seo关键词优化排名
  • 深圳做网站网络营销公司哪家好软件系统开发方案
  • 网站方案策划书18000字有公网ip 如何做一网站
  • 邵阳网站seo怎么使用模板建设网站
  • 网站开发要多长时间网站建设需求量