Given K <= 100 types of sticks, each stick i having Li units of length, and Pi as prize of the stick and there is an unlimited amount of sticks from each type. We have to connect multiple sticks together so that total length of chosen sticks is exactly N and total prize is small as possible.
I'm struggling to find any solution within the limits of the time limit — 1s, because of the length N which can reach up to 10^9. Can someone give me any techniques required to solve the problem(i know the solution with O(NK) time complexity-not good for time limit), or report if there aren't any.
Thank you :)
Auto comment: topic has been updated by ReadDead (previous revision, new revision, compare).
Are there any constraints about the length and price of sticks?
I have ridden two versions of the problem: - One is where for every i, 2 <= Li <= 1 000; - and for second one we know nothing about the lengths of sticks, but it guaranties that there is stick with length 1 and prize for any stick is 1.