Hi guys, as the title stated, I really need some help with a problem (It appeared in my country's OI years ago).↵
I remember it being a problem on Codeforces, the statement goes something like this:↵
↵
Given N knowledges, numbered from 1 to N, each knowledge i has a cost of S[i] for you to be proficient in it.↵
There are M tests, for each test from 1 to M, it gives you A[i] money, but it has a set of knowledges that require you to be proficient in all of it. Calculate the maximum benefit, if you learn knowledges optimally.↵
For example, ↵
<br>↵
N = 5↵
<br>↵
↵
1 2 2 1 3↵
<br>↵
M = 4↵
<br>↵
A[1] = 2, knowledge requirements of 1 : (1,2)↵
<br>↵
A[2] = 5, knowledge requirements of 2 : (2,3)↵
<br>↵
↵
A[3] = 1, knowledge requirements of 3 : (5)↵
↵
<br>↵
↵
A[4] = 1, knowledge requirements of 4 : (1)↵
↵
<br>↵
↵
The maximum benefit will be 3, since you learn knowledges (1,2,3) costs 1+2+2 = 5, and the tests 1,2,4 will give you 2+5+1 = 8↵
profit — cost = 8 — 5 = 3↵
↵
<br>↵
↵
Thanks for any help in advance!!!
I remember it being a problem on Codeforces, the statement goes something like this:↵
↵
Given N knowledges, numbered from 1 to N, each knowledge i has a cost of S[i] for you to be proficient in it.↵
There are M tests, for each test from 1 to M, it gives you A[i] money, but it has a set of knowledges that require you to be proficient in all of it. Calculate the maximum benefit, if you learn knowledges optimally.↵
For example, ↵
<br>↵
N = 5↵
<br>↵
<br>↵
M = 4↵
<br>↵
A[1] = 2, knowledge requirements of 1 : (1,2)↵
<br>↵
A[2] = 5, knowledge requirements of 2 : (2,3)↵
<br>↵
↵
The maximum benefit will be 3, since you learn knowledges (1,2,3) costs 1+2+2 = 5, and the tests 1,2,4 will give you 2+5+1 = 8↵
profit — cost = 8 — 5 = 3↵
↵
Thanks for any help in advance!!!
