# 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)