2056번: 작업

https://www.acmicpc.net/problem/2056


$O(nm)$

dp[i]=max(j<i)(dp[j])+t[i]

#include<cstdio>
int n, dp[10001], r;
int main() {
    scanf("%d", &n);
    for (int i = 1, t, x, y; i <= n; i++) {
        for (scanf("%d%d", &t, &x); x--;) {
            scanf("%d", &y);
            if (dp[i] < dp[y]) dp[i] = dp[y];
        }
        dp[i] += t;
        if (r < dp[i]) r = dp[i];
    }
    printf("%d", r);
    return 0;
}