Algoogle

Algorithm for Programming Contest

PKU 1949 Chores

Category: PKU Tag: dp

Chores

問題概要


解法


メモ化再帰
それぞれについて自分より前に処理するやつ全てを計算する.
計算結果はメモする.

コード


(1949.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <vector>

using namespace std;

int N, tim[10010];
int done[10010];
vector<int> P[10010];

int rec(int i){
    if(done[i]) return done[i];
    done[i] = tim[i];
    for(int j = 0; j < P[i].size(); j++)
        done[i] = max(rec(P[i][j])+tim[i], done[i]);
    return done[i];
}

int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        int t;
        scanf("%d %d", tim+i, &t);
        for(int j = 0; j < t; j++){
            int p; scanf("%d", &p);
            P[i].push_back(p-1);
        }
    }

    int ans = 0;
    for(int i = 0; i < N; i++) ans = max(ans, rec(i));
    printf("%d\n", ans);
    return 0;
}

Comments