背包
「HNOI2007」梦幻岛宝珠-背包dp
· ✏️ 1261 words · ☕ 3 mins read

给你 N 颗宝石,每颗宝石都有重量 wi 和价值 vi。要你从这些宝石中选取一些宝石,保证其总重量不超过 W ,且总价值最大。

请你输出最大的总价值。


「POI2012」Cloakroom-类背包dp
· ✏️ 605 words · ☕ 2 mins read

n 件物品,每件物品有三个属性 a[i],b[i],c[i] , (a[i]<b[i])

再给出 q 个询问,每个询问由非负整数 m , k , s 组成,问是否能够选出某些物品使得:

  • 对于每个选的物品 i ,满足 a[i]mb[i]>m+s

  • 所有选出物品的 c[i] 的和正好是 k