ContractWork
SRM 248 · 2005-06-21 · by NeverMore
SRM 248 · 2005-06-21 · by NeverMore · Dynamic Programming
Problem Statement
Problem Statement
Your company has a set of numTasks tasks that it wishes to complete. These tasks must be completed in order; that is to say, work on task j + 1 cannot begin until task j is complete. Your company has decided to contract the work to outside companies. There is a set of companies, each of which performs each of these tasks for a certain fee. Naturally, your company wants to spend as little as possible in accomplishing these tasks. Because each of these tasks is so complex, there's another restriction: One contract company cannot perform three tasks in a row for your company.
Create a class ContractWork containing a method minimumCost which takes aString[] costs and an int numTasks as input. Each element of costs is a string of numbers separated by exactly one space. The jth number in element i of costs represents the amount company i will charge to perform task j. Each string will contain exactly numTasks numbers. Clearly, the number of companies is the number of elements in costs. The method should return an int corresponding to the minimum cost incurred by your company while contracting out the tasks.
Create a class ContractWork containing a method minimumCost which takes a
Constraints
- costs will contain between 2 and 50 elements inclusive.
- numTasks will be between 2 and 50 inclusive.
- Each element of costs will contain exactly numTasks numbers, each separated by single spaces.
- Each number in costs will be an integer between 0 and 100, inclusive with no extra leading zeroes.
- Each element of costs will contain between 1 and 50 characters, inclusive.
Examples
0)
{"1 2 3", "4 5 6"}
3
Returns: 9
There are three ways to achieve the best answer. Company 0 can perform tasks 0 and 1 with Company 1 performing task 2, or, Company 1 can perform task 0 with Company 0 performing tasks 1 and 2, or finally, Company 0 can perform tasks 0 and 2, with Company 1 performing task 1. Any other combination gives a higher cost to your company.
1)
{"1 1 1 1", "1 1 1 1", "1 1 1 1"}
4
Returns: 4
2)
{"12 14 4 11 0 35", "44 41 1 1 0 15", "35 1 35 55 1 13", "0 0 0 0 0 0"}
6
Returns: 1
Lots of companies are willing to perform certain tasks for free...
3)
{"100 100 1", "1 1 100", "1 1 1"}
3
Returns: 3
4)
{"45 36", "79 34"}
2
Returns: 79
Submissions are judged against all 73 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ContractWork with a public method int minimumCost(vector<string> costs, int numTasks) · 73 test cases · 2 s / 256 MB per case