검은돌 트릭 (1) 썸네일형 리스트형 백준 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.. 이전 1 다음