Help me solving THIS PROBLEM from codeforces div-2 I couldn’t solve this problem during the contest.
First find all the connected components, as u can see, u can chhose atmost one or all the nodes/hoses of a particular connected component. Let C1,C2 , … , Ck be the connected components. Now define DP [ I ] [ Wt ] to be the max beauty selecting hoses till the Ci with weight limit (max allowed total weight) Wt. The answer to the problem will be DP [ K ] [ W ] where W is the given number in the problem.
For i from 1 to K, Wt from 1 to W :
To find DP [ I ] [ Wt ]:
-
U dont choose any hose from component I ( + DP [i-1][Wt] )
-
U choose all hoses from I ( + DP [ i-1][WT - sum_wt(Ci) ] + sum_beauty(Ci))
-
iterate thru all hoses in Ci one by one, let X be one of them ( + DP[i-1][wt-weight(X) ] + beauty[X] )
In case 2,3 check that WT - sum_wt(Ci),wt-weight(X) >= 0 .
1 Like
Two Hoses x and y are in the same friendship group if and only if there is a sequence of Hoses a1, a2, …, ak such that ai and ai + 1 are friends for each 1 ≤ i < k, and a1 = x and ak = y.
What does this line mean, and how it will be taken care of in your approach.
this means that x and y are in same connected component of the graph