[题解]KK2310 背盆

先按照性价比贪心一下。可以证明，贪心解和正解不会相差超过 $2w_i$ 个物品，所以相差的这些物品的总容量为 $2w_i^2$。所以可以在后面做一次 $O(n\times 2w_i^2)$ 的背包 DP。

对于证明上述性质，可以用调整法。

more >>

戳我看全文~ >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

一只蒟蒻<br><br>A Konjac