블 루 브리지 컵알고리즘 증가금속 채집 (트 리 동적 계획)
입력 형식 첫 줄 은 세 개의 정수 n, S 와 k 를 포함 하고 각각 노드 의 개수, 착지 번호, 로봇 의 개 수 를 대표 합 니 다.다음은 모두 n - 1 줄 로 줄 마다 길 을 설명 합 니 다.한 줄 에는 세 개의 정수 x, y 와 w 가 포함 되 어 있 는데 이것 은 x 번 노드 와 y 번 노드 사이 에 길이 있 음 을 나타 내 고 w 개 단위 의 에 너 지 를 소비 해 야 한 다 는 것 을 의미한다.모든 도 로 는 양 방향 으로 통행 할 수 있다.출력 형식 은 모든 노드 의 금속 을 채취 하 는 데 필요 한 최소한 의 에 너 지 를 나타 내 는 정 수 를 출력 합 니 다.샘플 입력 613, 1, 2, 3, 2, 4, 1000, 25, 1000, 16, 1000 샘플 출력 3004 샘플 은 모든 로봇 이 1 번 노드 에 착륙 한 다 는 것 을 의미한다.첫 번 째 로봇 의 주 행 경 로 는 1 - > 6 이 고 6 번 노드 에서 지구 로 돌아 가 에 너 지 를 1000 으로 소모 한다.두 번 째 로봇 의 주 행 경 로 는 1 - > 2 - > 3 - > 2 - > 4 로 4 번 노드 에서 지구 로 돌아 가 에 너 지 를 1003 으로 소모 한다.첫 번 째 로봇 의 주 행 경 로 는 1 - > 2 - > 5 로 5 번 노드 에서 지구 로 돌아 가 에 너 지 를 1001 로 소모 한다.데이터 규모 와 약정 본 문 제 는 10 개의 테스트 포인트 가 있다.테스트 포인트 1 ~ 2, n < = 10, k < = 5.테스트 포인트 3, n < = 100000, k = 1.테스트 포인트 4, n < = 1000, k = 2.테스트 포인트 5 ~ 6, n < = 1000, k < = 10.테스트 포인트 7 ~ 10, n < = 100000, k < = 10.도로 의 에너지 w 는 모두 1000 을 초과 하지 않 는 정수 이다.
문제 풀이 방향: dp [root] [k]: 루트 를 뿌리 로 하 는 서브 트 리 에 k (소문 자 k) 로봇 의 비용 을 표시 합 니 다.반드시 주의해 야 할 것 은 하나하나 의 수 를 하나의 전체 로 간주 해 야 한 다 는 것 이다.좋 은 트 리 dp, 오래 이 해 했 습 니 다.
(1) 처음에 dfs 가 어느 노드 에 도 착 했 을 때 아들 노드 가 없 으 면 로봇 은 여기 서 멈 출 수 있 습 니 다. dp [root] [k] 는 0 입 니 다.
(2) 만약 에 아들 노드 가 발견 되면 이 아들 노드 에 remain (remain 의 수치 범 위 는 0, 1,..., k) 개 로봇 을 고려 합 니 다. / / 서브 트 리 슨 에 로봇 이 머 물 지 않 았 다 면 모두 되 돌아 가 는 것 을 의미 합 니 다. 적어도 한 개의 dp [root] [k] + = dp [next] [0] + cost * 2 를 되 돌려 줍 니 다.for (remain = 1; remain < = k; remain +) {/ / dfs 가 첫 아들 이 되 었 을 때 나머지 아들 을 잠시 발견 하지 못 했 기 때문에 루트 노드 에 남 은 로봇 은 dp [root] [k] = min (dp [root] [k], dp [root] [k - remain] + dp [next] [remain] + remain * cost) 을 소모 하지 않 습 니 다.}
(3) dfs 가 깊 어 지면 서 새로운 아들 을 발견 할 때마다 업 데 이 트 를 할 때 앞의 모든 아들 의 상 태 를 고려 하여 이전 해 야 한다.이것 은 점진 적 인 과정 이다.예 를 들 어 두 번 째 아들 때 k = 1, remain = 1 이면 dp [root] [k] = min (dp [root] [k], dp [root] [k - remain] + dp [next] [remain] + remain * cost);사용 하 는 dp [root] [k - remain] 은 더 이상 0 이 아 닙 니 다. 먼저 첫 번 째 아들 을 방문 하고 루트 노드 로 돌아 가 야 하기 때 문 입 니 다.모든 아들 dfs 가 지나 간 후에 얻 은 dp [root] [m] 는 더 이상 변 하지 않 습 니 다.
자바 코드:
import java.util.ArrayList;
import java.util.Scanner;
/** * @author * */
public class Main {
private static int n;//
private static int s;//
private static int K;//
private static Edge[] edge;//edge[i]: i
private static boolean[] hasVisit;// ( )
private static int[][] dp;//dp[p][k]: p k 。
/** * @param args */
public static void main(String[] args) {
// TODO Auto-generated method stub
init();
dfs(s);
System.out.println(dp[s][K]);
}
private static void dfs(int root){
hasVisit[root]=true;//
for(int i=0;i<edge[root].ends.size();i++){//i root i
int next=edge[root].ends.get(i);//next root i
int cost=edge[root].weights.get(i);
if(hasVisit[next]){//
continue;
}else{
dfs(next);// dp[next][0]、dp[next][1]、...、dp[next][K];
for(int k=K;k>=0;k--){// 0
dp[root][k]+=dp[next][0]+2*cost;// son , ,
for(int remain=1;remain<=k;remain++){
int temp=dp[root][k-remain]+dp[next][remain]+remain*cost;// son remain
if(temp<dp[root][k]){
dp[root][k]=temp;
}
}
}
}
}
}
// (n、s、k、edge、dp、hasVisit)
private static void init(){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
s=sc.nextInt();
K=sc.nextInt();
edge=new Edge[n+1];
hasVisit=new boolean[n+1];
dp=new int[n+1][K+1];
for(int i=1;i<=n;i++){
edge[i]=new Edge();
}
for(int i=1;i<=n-1;i++){
int v1=sc.nextInt();
int v2=sc.nextInt();
int w=sc.nextInt();
edge[v1].ends.add(v2);
edge[v1].weights.add(w);
edge[v2].ends.add(v1);
edge[v2].weights.add(w);
}
sc.close();
}
}
class Edge{
ArrayList<Integer> ends=new ArrayList<Integer>();//
ArrayList<Integer> weights=new ArrayList<Integer>();//
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.