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
Let's initially include all colors. Now we want to remove a subset of colors with maximum total weight such that after blocking those squares, there are no gaps of length 2 or longer in the array. The only constraints are that we must not remove the colors $$$c[1]$$$ and $$$c[n]$$$, and that if colors $$$u$$$ and $$$v$$$ are adjacent in the array somewhere, then at most one of $$$u$$$ and $$$v$$$ must not be removed.
Build a graph where the vertices are colors (but $$$c[1]$$$ and $$$c[n]$$$ are excluded). We must choose a subset of vertices such that no two adjacent vertices are chosen. This is weighted maximum independent set. (And we can go the other way too, any graph can be built like this).
Meet in the middle. The way you typically do this is to take the first 20 vertices and brute force all independent sets that you can make using those vertices. Then take all other vertices and brute force all independent sets you can make using those.
Now we have some independent set $$$S$$$ made of the first 20. You want to quickly find the largest weight independent set $$$T$$$ of the rest of the vertices such that $$$T$$$ and $$$S$$$ are compatible. For $$$S$$$, list all the vertices of that must not appear in $$$T$$$. Now find maximum-over-subsets.