tree dp (2) 썸네일형 리스트형 백준 15681 - 트리와 쿼리 주어진 입력으로 트리를 구성한다. 그리고 그래프 탐색을 통해 해당 노드의 깊이도 저장하도록 한다. 그 후 탑다운 DP를 통해 해당 노드가 가지는 자식의 갯수를 계산하여 출력하도록 하면 된다. 전체 코드 더보기 #include using namespace std; vector al[100001]; int depth[100001]; int dp[100001]; int build_tree(int v); int main() { memset(dp, -1, sizeof dp); ios::sync_with_stdio(false); cin.tie(0); int v, rt, qry; cin >> v >> rt >> qry; for (int i = 0; i > g.. 백준 2056 - 작업 작업 간 선행관계가 제시되어 있으므로 작업들의 관계는 DAG가 되고 DP를 통해 각 작업을 끝내는데 필요한 최소시간을 찾아 더해주면 된다. 포레스트 형태에 대해 유의하여 구현한다. 전체 코드 더보기 #include using namespace std; using graph = vector; int finished[100001]; int fee[100001]; int memo[100001]; int dp(int node, graph &al); int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); int n; cin >> n; memset(memo, -1, sizeof memo); graph task(n + 1); for (int i = 0;.. 이전 1 다음
