PROBLEM LINK:
Author: Erfan alimohammadi
Tester & Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy-medium
PREREQUISITES:
DP
PROBLEM:
There are N songs (numbered 1 through N) and M albums (numbered 1 through M) available. For each valid i, the i-th song has greatness v_i, price p_i and belongs to the album a_i. For each valid i, the i-th album has price b_i. If we buy an album, then all songs from this album count as bought. It is also possible to buy any songs individually.
Your task is simple ― given the budget P, calculate the maximum total (sum of) greatness of songs we can buy.
1 \leq N,M,P \leq 1000
EXPLANATION
Let’s solve it in the following way, let’s create a list of all songs such that all songs which are from the same album are consecutive. Let’s build then our dp table.
dp(i,B) denotes the maximum total greatness we can achieve considering only the first i songs and spending exactly B.
dp(0,0)=0 \,\,\,\,\, This is our initial case.
Now when we are processing some song let’s say the i_{th} one we have 2 options either to buy it or not. So :
dp(i,B) \, = \, max(\, dp(i - 1,B) \, , dp(i-1,B-p_i)+v_i)
The first term indicates not buying the song, whereas the second indicates buying it. Of course, we shouldn’t try buying the song if B<p_i
As you can see we solved the problem considering buying only songs individually. How can we add the possibility of buying a complete album?
Not so hard, after processing the last song from a certain album. We should add try buying the complete album and updating our dp table. Please make sure again that all songs which are from the same album are consecutive.
Let’s assume that the current song x_{th} one is the last song of some album. For each possible B
dp(x,B)=max(dp(x,B)\, , \,dp(y,B-album\,price)+totV_album)
Looks confusing and not understandable
By y we denote the first song preceding the x_{th} and belonging to different album. We can only build a solution containing some album fully bought only if the sub-solution (the sub-problem) we are building on top of it has no song bought from that album (since each song can be bought only once).
It’s clear that totV_{album} denotes the greatness sum of the album songs.
Complexity: O(N*P)