ioi (2) 썸네일형 리스트형 백준 1805번 나무수송 https://www.acmicpc.net/problem/1805 dp[i][j][k] 를 i번 노드를 루트로 하는 서브트리에 대해 목공소를 정확히 j개를 짓고 서브트리의 모든 나무가 i번 노드까지 이동했을때 k개의 나무가 목공소를 거치지 않은 경우의 최소 운반비 로 정할 수 있다.목공소의 여러 조합에 따른 k의 가짓수를 정확히 알수는 없지만 검은돌 트릭에 따라 노드를 합치는데 드는 비용이 생각보다 적기에 시간 안에 돌 수 있다는 계산으로 일단 코드를 짜 보았고 TLE를 받았다. #pragma GCC optimize("Ofast")#include using namespace std;int k;vector>> graph;vector w;vector>> dp;void dfs(int node){ dp[n.. 백준 8872번 빌라봉 https://www.acmicpc.net/problem/8872 8872번: 빌라봉첫째 줄에는 N, M, L이 주어진다. 둘째 줄부터 M개 줄에는 A[i] B[i] T[i]가 주어진다. 1 ≤ N ≤ 100,000 0 ≤ M ≤ N-1 0 ≤ A[i], B[i] ≤ N-1 1 ≤ T[i] ≤ 10,000 1 ≤ L ≤ 10,000www.acmicpc.net 일단 각각의 연결된 빌라봉들이 트리형태이니 연결된 빌라봉들마다 한번씩 dfs를 돌려야 할 것 같다.그리고 그 트리가 다른 트리들과 연결될때는 하나의 노드에서만 연결되고 트리에서 그 노드로부터 가장 먼 정점의 거리가 가장 짧게되는 정점을 잡으면 된다.이때 트리마다 나오는 이 거리들을 그 트리의 가중치로 두면 각 트리를 정점으로 하는 큰 트리가 만들어 .. 이전 1 다음
