solution

暴力分都骗全了
A: DFS骗分70
B: 单调队列+打表骗分
60
C: 暴力换根+统计答案骗分*20
总分:(70 + 60 + 20 = 150)

A(分段状压)

题意简述:

给你K个数量为1的物品及其重量,你有N的数量限制和M的重量限制,求背包最大重量

解:

(K<=40)没法状压,但是(K<=20)是没问题的
考虑分成两半进行状压
我们将一半算好,根据它们的个数(cnt)把它们的重量存进vector里面(V[cnt].push_back(W))
剩余的集合每算一个就在第一个集合中找出cnt满足要求且值(<=M-W_i)的最大值,加起来,Ans再取一个(max)值即可

B

原文地址:https://www.cnblogs.com/qwqq/p/11757070.html