StampsCollection
SRM 418 · 2008-09-20 · by Rydberg
SRM 418 · 2008-09-20 · by Rydberg · Dynamic Programming, Graph Theory
Problem Statement
Problem Statement
You have decided to sell your stamp collection, which consists of n stamps numbered 0 to n-1. You have already found some buyers. The i-th buyer wants to buy the stamps listed in demand[i]. This will be a space-separated list containing either one or two stamps. He is willing to pay a total of price[i]. If he wants to buy two stamps, he will not agree to buy only one of them.
To make this task simpler, for each stamp, there will be no more than two buyers who want to buy it. Return the maximum amount of money you can get from selling your stamps.
To make this task simpler, for each stamp, there will be no more than two buyers who want to buy it. Return the maximum amount of money you can get from selling your stamps.
Notes
- You don't have to sell all of your stamps.
Constraints
- n will be between 1 and 50, inclusive.
- demand will contain between 1 and 50 elements, inclusive.
- price will contain the same number of elements as demand.
- Each element of demand will be a space-separated list of one or two distinct integers.
- All numbers in demand will be between 0 and n-1, inclusive, with no leading zeroes.
- All numbers in price will be between 1 and 1000000, inclusive.
- For each stamp, there will be at most 2 buyers who want to buy it.
Examples
0)
10
{"0 4"}
{3}
Returns: 3
There is only one buyer, so all we can do is to sell two stamps.
1)
2
{"1 0","0"}
{3,5}
Returns: 5
There are two buyers, but both want to buy stamp 0.
2)
3
{"0 1","0 2","1 2"}
{10,11,12}
Returns: 12
Only one buyer can get what he wants - we choose the third one, who is willing to pay the most.
3)
3
{"0","1 0","1 2"}
{5,9,5}
Returns: 10
Although the second buyer will pay the most, it is better to choose the first and third buyers.
4)
20
{"0 1","1 2","2 3","3 0","4 5","5 6","6 4","8","8","9","9 10","10 11","11 12","12"}
{3,7,4,1,3,3,1,5,6,5,18,10,1,5}
Returns: 40
Submissions are judged against all 177 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StampsCollection with a public method int sell(int n, vector<string> demand, vector<int> price) · 177 test cases · 2 s / 256 MB per case