Connection Status:
Competition Arena > ShopPositions

ShopPositions

SRM 667 · 2015-08-28 · by lg5293

SRM 667 · 2015-08-28 · by lg5293 · Dynamic Programming
Class Name: ShopPositions
Return Type: int
Method Name: maxProfit
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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
0)
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.

1)
1
5
{1000, 5, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 1000
2)
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.

3)
2
2
{
 12,11,10,9,8,7,
 6,5,4,3,2,1
}
Returns: 24
4)
3
3
{
  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

Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ShopPositions with a public method int maxProfit(int n, int m, vector<int> c) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous