현재 건물까지 건설하려면 이전 건물을 모두 지어야 합니다.
$i$번째 건물까지 짓는 시간을 $\mathrm{total}\left(i\right)$, $i$번째 건물을 짓는 데 걸리는 시간을 $t_i$, $i$번째 건물 이전에 지어야 하는 건물들의 번호 집합을 $\mathcal{D}_i$라 하면
$$ \mathrm{total}\left(i\right)=\begin{cases} t_i & \left(\mathcal{D}_i = \varnothing\right) \\ t_i + \underset{j\in\mathcal{D}_i}{\mathrm{max}}\left(t_j\right) & \mathrm{otherwise.} \end{cases} $$
따라서 각 건물을 깊이 우선 탐색하면서 $\mathrm{total}\left(i\right)$의 값을 저장해 두는 동적 계획법 풀이를 생각할 수 있습니다.
최댓값을 계산하기 위해 모든 건설 순서 규칙을 최대 한 번씩만 확인하므로 시간복잡도는 $O\left(K\right)$입니다.
코드
fn dfs_cache(building: &[(u32, Vec<usize>)], cache: &mut [u32], root: usize) {
if building[root].1.is_empty() {
cache[root] = building[root].0;
} else {
let mut max_before = 0;
for &before in &building[root].1 {
if cache[before] == u32::MAX {
dfs_cache(building, cache, before);
}
max_before = max_before.max(cache[before]);
}
cache[root] = max_before + building[root].0;
}
}
fn solve(building: &[(u32, Vec<usize>)], last: usize) -> u32 {
let mut cache = [u32::MAX; 1000];
dfs_cache(building, &mut cache, last);
cache[last]
}