| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | Dominater069 | 154 |
| 8 | awoo | 154 |
| 10 | luogu_official | 150 |
Hey, Everyone I am unable to understand that how should I apply knapsack in this problem
http://codeforces.net/problemset/problem/741/B
Because it contains different groups.Thus Mine complexity is coming O(W*N*N).I saw the editorial but unable to understand the solution.Can anyone explain ?
Sorry if I misunderstood your problem regarding the solution,but I will try to explain it entirely. Firstly,imagine the relationships betweeb Hoses as a graph.2 hoses are in the same friendship group if they are in the same connected component.You can run a dfs/bfs to find all the connected components.Why does it matter?If two Hoses are n the same friendship group we can't take one without the other,so we imagine each group as a super-Hose with the weight that is the sum of the weights of the hoses of the group,and the beauty the sum of the beauties of the hoses in the group. Secondly,we have at most n items(there can't be more than n connected components) so we can just apply the classical knapsack in O(n*k):
dp[ i ][ j ]=max(dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ])where Sweight[ i ],Sbeauty[ i ] are the weight and the beauty of i-th super hose.You can optimize knapsack's memory by always holding only the current and the previous line or having just an array and going with the j index in reversed order (from w to 1) but I don't believe this is essential if you have enough memory.But I think you didn't cover the case suppose we have three groups (1,2,3),(4,5),(6,7) Now As we can take maximum 1 from each group or can take all elements of the group.Now suppose maximum beauty with weight constraint come from this arrangement (2,4,5,7 i.e 2 nd from 1st set ,all from 2nd set,7 from last set),I hope you understand.
Yeah,I'm sorry.I didn't solve the problem so I wasn't that careful at the statement.Each time you try to insert a super hose,you try to insert each hose that is from its group.So the recurrence becomes
dp[ i ][ j ]=max((dp[ i-1 ][ j ],dp[ i-1 ][ j-Sweight[ i ] ]+ Sbeauty[ i ]), max{dp[ i-1 ][j-weight[ x ] ]+beauty[ x ]}),where x is successively,each hose from i-th group.Finally done thanks!