ShopPositions | Topcoder Archive

Problem Statement

Carol is starting a new taco shop business. She is going to open some taco shops in a block of buildings. The blocks consists of n adjacent buildings in a row. Each building has exactly m floors. The buildings are numbered 0 through n-1 in order.

Carol can open between 0 and m taco shops in each building (as there can be at most one taco shop per floor in each building). For each taco shop, the profit P[x][y] will depend on two factors:

the number x of the building that contains this taco shop
the total count y of taco shops in that particular building and in buildings adjacent to that building (including this particular taco store)

You are given the ints n and m. You are also given the profits as defined above, encoded into a int[] c. For each x between 0 and n-1, and for each y between 1 and 3m, the profit P[x][y] is given in c[x*3*m+y-1].

It is guaranteed that the profits don't increase as y increases. That is, for each valid x and y, P[x][y] will be greater than or equal to P[x][y+1]. Note that the profit is for a single store. For example, if there are three taco stores in building 7 and no other stores in buildings 6 and 8, each of these three taco stores will bring the profit P[7][3].

Determine and return the maximum total profit that Carol can gain from opening the taco shops.

Definition

Class:: ShopPositions
Method:: maxProfit
Parameters:: int, int, int[]
Returns:: int
Method signature:: int maxProfit(int n, int m, int[] c)
(be sure your method is public)

Constraints

n will be between 1 and 30, inclusive.
m will be between 1 and 30, inclusive.
c will have exactly n*3*m elements.
Each element of c will be between 1 and 1,000, inclusive.
For each x between 0 and n-1, the sequence c[3*m*x], c[3*m*x + 1], ..., c[3*m*(x+1) - 1] will be sorted in nonincreasing order

Examples

```
1
```
```
5
```
```
{100, 90, 80, 70, 60, 50, 40, 30, 20, 10, 1, 1, 1, 1, 1}
```
```
Returns: 300
```
Carol has 1 building with 5 floors. Building one shop will get her a profit of 100, while building two shops will get a profit of 90*2. The optimal strategy in this case is to build 5 taco shops, for a profit of 60*5=300.

{1000, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

Returns: 1000

```
3
```
```
1
```
```
{
  7,6,1,
  10,4,1,
  7,6,3
}
```
```
Returns: 14
```
The optimal strategy here is to open one taco store in building 0 and one taco store in building 2.

{
 12,11,10,9,8,7,
 6,5,4,3,2,1
}

Returns: 24

{
  30,28,25,15,14,10,5,4,2,
  50,40,30,28,17,13,8,6,3,
  45,26,14,14,13,13,2,1,1
}

Returns: 127

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.