Stuck with a dp/greedy problem :(

Правка en2, от viper1234, 2022-11-12 01:57:24

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

Теги dp, greedy, algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский viper1234 2022-11-12 01:58:47 15 Tiny change: 'onstraints:\n- 1 <= N' -> 'onstraints\n- 1 <= N'
en2 Английский viper1234 2022-11-12 01:57:24 23
en1 Английский viper1234 2022-11-12 01:56:22 1013 Initial revision (published)