An interesting problem

Revision en2, by Loserinlife, 2024-04-21 17:27:29

Given n block numbered from 1 to n, you start at block 1 and want to reach block n. From block[i] you can move to block i + 1

or block i + 2. Each block has a colour c[i] associated with it. There are m colour, each colour has cost w[i]. At the start,

you decided to purchase a subset S of colour, the cost of which is the total w[i] of all i chosen. Find the minimum cost of such

subset S that you are able to go from 1 to n stepping on only blocks with a chosen color. (c[i] is in S)

Input:

8 8

6 4 1 5 2 8 4 2

19 15 13 10 3 9 13 13

Output: 37 (S is {2, 6, 4, 5})

Thanks!

N <= 3e5, M <= 40

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Loserinlife 2024-04-21 17:27:29 25 Tiny change: 'n\nThanks!' -> 'n\nThanks!\n\nN <= 3e5, M <= **40**'
en1 English Loserinlife 2024-04-21 17:20:24 629 Initial revision (published)