Question

A state is divided into R*C cities.The government has
launched an initiative to find the cities which are
dominated by coders. Each city may or may not have
coders residing in it. If the city is dominated by coders,
it is marked with 1 else it is marked with O. Two cities
are termed as connected cities if they both are
dominated by coders and can be reached by moving
vertically, horizontally, or diagonally.​

Answer 1

Answer:

Given n cities: x1, x2, …… xn: each associated with T[i] (treasure) and C[i] (color). You can choose to visit a city or skip it. Only moving in the forward direction is allowed.When you visit a city you receive the following amount:

A*T[i] if the color of visited city is the same as color of previously visited city

B*T[i] if this is the first city visited or if the color of the visited city is different from the color of the previously visited city.The values of T[i], A and B can be negative while C[i] ranges from 1 to n.

We have to compute the maximum profit possible.

Examples:

Input : A = -5, B = 7

Treasure = {4, 8, 2, 9}

color = {2, 2, 3, 2}

Output : 133

Visit city 2, 3 and 4. Profit = 8*7+2*7+9*7 = 133