Can someone help me with this problem, any help will be appreciated.
Problem Statement: Bob wants to purchase N pens and so has prepared a list of shops that sell the pens. Each shop charges a different price per pen and has a limited quantity available in stock. Along with the price of the pen, each shop charges fixed delivery fees irrespective of how many pens are bought. Write a program to help Bob get the N pens as cheaply as possible.
Input Format: The first input line has two integers: N, the number of pens Bob needs, and S, the number of shops. Next, S lines have 3 integers, Q, P, and D, where Q is the stock of pens available at the shop, P is the price per pen and D is the delivery fee.
Output Format: A single line of output has an integer, which is the minimum amount Bob has to spend to purchase N pens.
Constraints
1 <= N <=10000
1 <= S <= 100
0 <= 0 <= 10000
0 <= P<= 10000
O<= D <= 1000000
N<= 01+Q2+...+Qs
Auto comment: topic has been updated by viper1234 (previous revision, new revision, compare).
Auto comment: topic has been updated by viper1234 (previous revision, new revision, compare).
Write DP[N][S] — minimum cost to get N pens if we use first S stores. A trivial transition would work in O(N) — simply check all dp[i][S — 1]. Now, let's notice that the cost function is ( N — i) * P + Q + dp[i][S — 1], with an edgecase if we buy no pens. The above cost function js a linear function, so you can use Li-Chao to get O(NSlogN) If you can spend some more time and prove monotonicity of requests to the linear function, you can get O(NS) using CHT with two pointers
If we sort the shops in the increasing order of prices, then we are iterating from the first index in knapsack style, if we are taking this shop , we must take maximum pens from it , since if we are paying dues and we have some benifit then it will be max if we take maximum pens from this shops or just dont take