There are $N$ jobs, each job $i$ has a single prerequisite job $P_i$ that must be done before, except for a global root job which has no prerequisite. Each job takes $T_i$ time to be finished, and if a job is finished at time $t$ it contributes with a penalty of $t * U_i$, where $U_i$ is the i-th job's penalty coefficient. What is the minimum penalty for finishing all jobs?↵
↵
Constraints: $N <= 2 * 10^5$, everything is integer and non-negative↵
↵
Note: only a single task can be performed at a time (there is no concurrent work / task parallelism)↵
↵
-----↵
Any ideas on how to solve this? I was thinking of performing some kind of backtracking over all possible topological orderings of the DAG + some kind of extremely heavy pruning, but I still haven't figured out yet a good pruning strategy to avoid exponential time. I also thought of using DP, but then I need to use bitmasks to keep track of unvisited nodes, which leads to exponential time.↵
↵
↵
Constraints: $N <= 2 * 10^5$, everything is integer and non-negative↵
↵
Note: only a single task can be performed at a time (there is no concurrent work / task parallelism)↵
↵
-----↵
Any ideas on how to solve this? I was thinking of performing some kind of backtracking over all possible topological orderings of the DAG + some kind of extremely heavy pruning, but I still haven't figured out yet a good pruning strategy to avoid exponential time. I also thought of using DP, but then I need to use bitmasks to keep track of unvisited nodes, which leads to exponential time.↵
↵
