BOJ 2056 작업

 

문제 링크 : https://www.acmicpc.net/problem/2056

2056번: 작업

 

선행 관계가 작업 번호 순으로 주어지니 딱히 전처리할 것들은 없다.

 

dp[i] 는 i 번째 작업을 마칠 수 있는 최소 시간으로 정의한다.

$a[i]$ 를 i 번 작업에 소요되는 시간, $S_i$ 를 i 번 작업에 필요한 선행 작업이라 할 때,

다음 관계식이 성립한다.

$$dp[i]=\underset{j\in S_i}{max}dp[j]+a[i]$$ 

#include<bits/stdc++.h>

using namespace std;

vector<vector<int>> info;
vector<int> dp;

int main(){
    int n; scanf("%d",&n);
    dp=vector<int>(n+1);
    info=vector<vector<int>>(n+1);
    
    for(int i=1;i<=n;i++){
        int t; scanf("%d",&t);
        info[i].push_back(t);
        int k; scanf("%d",&k);
        for(int j=0;j<k;j++){
            int c; scanf("%d",&c);
            info[i].push_back(c);
        }
    }
    
    dp[1]=info[1][0];
    for(int i=2;i<=n;i++){
        int x=0;
        for(int j=1;j<info[i].size();j++)
            x=max(x, dp[info[i][j]]);
        dp[i]=x+info[i][0];
    }
    
    int ans=0;
    for(int i=2;i<=n;i++)
        ans=max(ans, dp[i]);
    printf("%d\n",ans);
}

 

info[i][0] 는 i 번 작업에 소요되는 시간.

info[i][1] ~ info[i][sz-1] 은 선행 작업들의 번호이다. ( sz=info[i].size( ) )