Codeforces Gym 101002 H. Jewel Thief 题解

题意

类似于一个背包,空间为$M$,有$N$个物品,第$i$个物品体积为$w_i$,价值为$c_i$,求价值之和的最大值。
其中,$1 \leq n \leq 100000$,$1\leq m \leq 300000$,$1\leq w_i \leq 3$,$1\leq c_i \leq {10}^9$

思路

首先注意到$n,m$非常大,所以普通的背包是肯定不行的,那么考虑从小数据(每个物品的体积)入手。
发现:体积只有$1,2,3$三种可能,那么就分类讨论就好了。
首先,把所有物品按照体积分为$3$类。
然后每一类的物品按照价值排序(从大到小)(因为同种体积,价值越大越好)。
设$f[i]$表示空间为$i$的目前价值之和的最大值。

评论

  1. Join some of parents and share your content and develop a relationship by bloggers.
    This is the same goal get for particular customers.
    That last thought is actually definitely an article by itself. https://918kiss.poker/casino-games/71-joker123

    4月前
    2019-5-18 16:51:52

发送评论


				
上一篇
下一篇