2056번: 작업
수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해
www.acmicpc.net
위상정렬 공부다가.. 결국 DP로 처리한다..
위상정렬이 어렵네..
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class BOJ2056 {
static int N;
static int[] D;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("res/input_boj2056.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long Start = System.currentTimeMillis();
StringTokenizer st;
N = Integer.parseInt(br.readLine());
D = new int[N+1];
int a, b, c;
int res = 0;
for (int i = 1; i <= N ; i++) {
st = new StringTokenizer(br.readLine());
c = Integer.parseInt(st.nextToken());
a = Integer.parseInt(st.nextToken());
for (int j = 1; j <= a ; j++) {
b = Integer.parseInt(st.nextToken());
D[i] = Math.max(D[i], D[b]);
}
res = Math.max(res, D[i]+= c);
}
System.out.println(res);
}
}