其实我早就会写多重背包了……只不过是写成做多次01背包而已……
看着大爷秒题，我心中感到自己好弱啊。
于是我就来理解一下多重背包的单调队列做法，并记录在这里。
对于一个物品有个数限制的背包，我们考虑状态转移方程：
f[now][j]=max(f[last][j],f[last][j-w[i]*k]+c[i]*k)，其中w[i]为重量，c[i]为价值。
感觉要枚举i,j,k，然后时间复杂度就爆炸了……
怎么办？用单调队列！
因为当我们取到了最大的f[last][j-w[i]*k]+c[i]*k时，再往下取k就没有意义了（不可能大于这个值）
所以我们维护一个单调队列，使队首为最大值，每次把不符合的队首删去，同时把队尾小于我们枚举的f[last][j-w[i]*k]+c[i]*k删去。
队列中存的是k，也就是记录当前取了多少个该物品，即可。
下面是一道例题。
----------------------------------------------------------------
超市购物
Description
Bob家附近新开了一家超市。最近，超市开展了促销活动。
超 市共出售N种不同的商品，编号为1…N。不同的物品对Bob来说有不同的价值，第i种物品每一个的价值为Wi。而每种商品的售价也不相同，第i种物品的单 价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光，决定每种商品每位顾客最多只能买Li个。现在，Bob共有M元，他想知道在花费 不超过M元的情况下，能买到的商品价值和最大为多少？
超 市共出售N种不同的商品，编号为1…N。不同的物品对Bob来说有不同的价值，第i种物品每一个的价值为Wi。而每种商品的售价也不相同，第i种物品的单 价为Ci元。同一种商品可以买多个。超市经理为了避免某些商品被一抢而光，决定每种商品每位顾客最多只能买Li个。现在，Bob共有M元，他想知道在花费 不超过M元的情况下，能买到的商品价值和最大为多少？
Input
第1行两个整数N和M，分别表示商品的种数与Bob现有的钱数。
接下来N行每行为三个整数Ci,Wi,Li，分别表示第i种商品的单价，单个的价值，最多可购买的件数。
接下来N行每行为三个整数Ci,Wi,Li，分别表示第i种商品的单价，单个的价值，最多可购买的件数。
Output
输出只有一行，为Bob能买到的商品最大价值和。
Sample Input
5 30
3 1 3
1 4 1
8 10 3
4 7 2
2 2 4
3 1 3
1 4 1
8 10 3
4 7 2
2 2 4
Sample Output
42
Hint
20%的数据：N≤30，M≤10000，Li≤500；
70%的数据：N≤50，M≤500000，Li≤2000；
100%的数据：N≤50，M≤500000，Li≤500000；
70%的数据：N≤50，M≤500000，Li≤2000；
100%的数据：N≤50，M≤500000，Li≤500000；
----------------------------------------------------------------
Code:
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,l[55],c[55],w[55],f[2][500005],q[500005];
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&c[i],&w[i],&l[i]);
}
for(int i=1;i<=n;i++){
int now=i%2,last;
last=now^1;
for(int j=0;j<c[i];j++){
int Rear=1,Front=1;
q[1]=0;
for(int k=0;k*c[i]+j<=m;k++){
while(Front!=Rear && k-q[Front]>l[i])Front++;
f[now][k*c[i]+j]=max(f[last][k*c[i]+j],f[last][q[Front]*c[i]+j]+w[i]*(k-q[Front]));
while(Front<=Rear && f[last][q[Rear]*c[i]+j]+w[i]*(k-q[Rear])<=f[last][k*c[i]+j])Rear--;
q[++Rear]=k;
}
}
}
printf("%d\n",f[n%2][m]);
return 0;
}
Sep 19, 2021 06:21:45 PM
Winters tend to be incomplete without having snuggling within the warm covers. Clean individuals soft covers and pillows before you decide to put all of them into make use of. Drop them within the washing device and clean them according to their manufacturers’ directions. If a person don’t would like the blankets to obtain dull, then toss a tennis games ball within the washing device before running force cycle. You can observe the difference since the feathers won’t stay together as well as won’t really feel lumpy, whatsoever.
Jan 19, 2025 09:40:56 PM
Nice post. I was checking constantly this blog and I am impressed! Extremely helpful information specially the last part I care for such info a lot. I was seeking this particular information for a very long time.
Jan 19, 2025 10:11:09 PM
Right here is the perfect written about for ages. Wonderful stuff, just wonderful.
Jan 19, 2025 10:11:54 PM
You won’t even have to rolling.
Jan 19, 2025 10:21:15 PM
it shouldn’t result in a headache.When you choose our scrap car removal services, you’re choosing to make it simple. We make the process of selling your scrap car painless, while getting you MORE cash for your car.
Jan 19, 2025 10:27:05 PM
Right here is the perfect website for everyone who would like to find out about this topic. You realize a whole lot its almost tough to argue with you (not that I personally will need to…HaHa). You certainly put a new spin on a subject which has been written about for ages. Wonderful stuff, just wonderful.
Jan 19, 2025 10:27:38 PM
Right here is the perfect website for everyone who would like to find out about this topic. You realize a whole lot its almost tough to argue with you (not that I personally will need to…HaHa). You certainly put a new spin on a subject which has been written about for ages. Wonderful stuff, just wonderful.
Jan 19, 2025 10:27:57 PM
It won’t prevent us from paying cash for scrap cars.Does it matter if the car has one or more flat tires? No, we can inflate any tires if necessary to help facilitate getting it on our truck, and we buy junk vehicles that don’t even have wheels, so what your car sits on is never an issue.Can I remove certain parts from the vehicle, for example, the tires and wheels or the stereo or battery? Yes, and we can discuss those options with you, but remember that this will impact the size of your cash payment.How much cash will you give me for my car? We base our quotes on real time data which includes current metal prices, the weight of your vehicle, the model year and how many kilometers are on the odometer.Is the offer contingent on the condition of the vehicle? No, you will be quoted a price based on the criteria in the question above. The quote won’t change even when the driver observes the car.
Jan 19, 2025 10:28:15 PM
That’s one of the reasons why selling a vehicle with mechanical issues or electrical issues can so very difficult. No one wants to put money into someone else’s issues. Unless you can convince a buyer that your car is a sound investment, it’s a better idea to sell your scrap car to More Cash For Scrap instead.Junk-truck-buyerWhat Determines the Value of My Vehicle? When we buy a scrap car though, we considering everything. Not just the vehicle’s weight, but things like it’s components, how it was maintained before becoming a scrap car, etc. So we’ve comprised this list to help explain what exactly determines the worth of your scrap car, truck, SUV, or van.
Jan 19, 2025 10:28:41 PM
Age of the vehicle Overall condition Drivability (if any) Value of spare parts Collectability Make of the vehicle Model of the vehicle Kilometers (if you are able to retrieve them) If you’ve recently been made offers on your junk vehicle, and weren’t impressed by them, give us a call. We can almost always offer MORE cash for scrap cars than any other scrap car removal company in Vancouver. We will take the time to explain where the value lies in your vehicle, and why. That way, even if you don’t accept our offer, you know what you scrap vehicle is truly worth.Instant Scrap Car Removal Offers & Same Day Vehicle Pick Up scrap-car-buyer-vancouver It’s quick and easy and totally free. Plus, we offer the top cash paid for selling your car to us! You have nothing to lose and MORE cash to gain.Just give us a call today. An in-person appointment may be scheduled, but it’s not normally necessary.
Jan 19, 2025 10:28:59 PM
For any vehicle that is pushing towards the end of its life cycle, there’s More Cash For Scrap. We buy vehicles with ANY kind of mechanical problems, while still paying you top dollar!That’s why we’ve been the best local scrap car buyer since 2005. And it’s why we’ll continue to be for many more years to come. We believe in paying MORE cash for scrap cars because when you recycle a vehicle, you help keep our province beautiful. You give back, so we give back too!We Buy Vehicles in ANY Condition with ANY Problem! We honestly don’t care what is wrong with your vehicle.
Jan 19, 2025 10:29:18 PM
Besides, no one else will pay your more cash for scrap cars than us! We are always happy to answer any questions you may have about your junk car or our services. Give us a call or text today. We are always ready to help!Recent Scrap Car Removals in Vancouver BC 2000 Mazda Protege With Blown Transmission – Kitsilano, Vancouver V6K 3E6 1981 Chevy Blazer That Won’t Start Anymore- East Vancouver V5L 5C9 2002 Mistubishi Eclipse With Catastrophic Front End Body Damage- False Creek, Vancouver V6A 3Z7 2008 Dodge Durango That Had The Engine Seize After Major Oil Leak – Jericho Beach, Vancouver V6R 1B5 1999 Ford Mustang GT With High Kilometers And Some Minor Interior Mold – West End, Vancouver V6G 1J6 2010 Ford Fusion with Severe Collision Damage – East Vancouver V5L 2C3 1992 Honda Accord With Over 340,000kms On It- Kerrisdale, Vancouver V6M 3W9 VANCOUVER LOCATIONS Burnaby Coquitlam Delta Langley Maple Ridge New Westminster North Vancouver Pitt Meadows Port Coquitlam Port Moody Richmond Squamish Surrey Vancouver West Vancouver Whistler White Rock FRASER VALLEY LOCATIONS Abbotsford Chilliwack Hope Mission RECENT BLOG POSTS MORE Cash for Scrap Cars in Vancouver Hyundai & Kia Engine Problems Canada How to Get Rid of Old Car for Cash Vehicles Noises You Shouldn’t Ignore Recycling My Car in Vancouver
Jan 19, 2025 10:29:38 PM
We Support Other Local Vancouver Companies: We fully support other local Vancouver based businesses. We live and work in Vancouver and exclusively utilize Vancouver scrap dealers, metal recyclers, vancouver salvage yards and car recyclers. This way we process your car in the most efficient and environmentally responsible manner. This way we get the most out of the cars we’re scrapping, while strengthening our bonds with other small businesses in the community.5.Eco-Friendly Car Recycling : We follow municipal and provincial laws when we recycled cars for cash.
Jan 19, 2025 10:36:45 PM
This submit couldn’t be written a great deal better! Looking through this post reminds me of my previous roommate!
Jan 19, 2025 10:47:38 PM
We Provide INSTANT Cash Offers on Junk Cars in Vancouver It’s quick, easy and totally free. You have nothing to lose and only MORE cash to gain. Just give
Jan 19, 2025 10:54:38 PM
Make scrap car removal specialists 24/7
Jan 19, 2025 10:57:07 PM
Services Locations than any other scrap car buyer in Metro Vancouver.
Jan 19, 2025 11:12:34 PM
Or perhaps that daily driver is actually driving you crazy because when it’s got over 300,000 kms on it, you know something is going to fail.
Jan 19, 2025 11:15:49 PM
it was maintained before becoming a scrap car, etc. So we’ve comprised this list to help explain what exactly determines the worth of your scrap car, truck, SUV, or van.
Jan 19, 2025 11:18:51 PM
We also abide by general car recycling policies to ensure that every vehicle is scrapped in the most environmentally friendly way possible. Not only is it the right thing to do, it’s how we get the most out of every vehicle. This means keeping more of your scrap car out of the landfill, and reusing, repurposing, or recycling the rest. It’s just one of the ways we help to keep Vancouver green and clean, just the way we like it!Eco-Friendly Car Recycling in Vancouver When it comes to recycling cars for cash, no one does it better than we do. We are truly the experts at scrap car removal.
Jan 19, 2025 11:31:58 PM
Plus, we pay MORE cash for scrap cars than anyone else in the junk car buying industry. Since 2005, Vancouver clients have trusted us for all of their scrap car removal needs to us. And when you have connections with local businesses like we do, you’re guaranteed to get top dollar. That’s why you should choose to recycle your car with More Cash For Scrap. It’s why we can proudly say that nobody pays MORE cash for scrap cars than we do!
Jan 19, 2025 11:36:18 PM
It won’t prevent us from paying cash for scrap cars.Does it matter if the car has one or more flat tires? No, we can inflate any tires if necessary to help facilitate getting it on our truck, and we buy junk vehicles that don’t even have wheels, so what your car sits on is never an issue.Can I remove certain parts from the vehicle, for example, the tires and wheels or the stereo or battery? Yes, and we can discuss those options with you, but remember that this will impact the size of your cash payment.How much cash will you give me for my car? We base our quotes on real time data which includes current metal prices, the weight of your vehicle, the model year and how many kilometers are on the odometer.Is the offer contingent on the condition of the vehicle? No, you will be quoted a price based on the criteria in the question above. The quote won’t change even when the driver observes the car.