超时的 dp

f(i) 记录任务 i 及后续需要花多少时间做完。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;
int n;
int a[MAXN + 5];
vector<int> e[MAXN + 5];
int f(int u)
{
    int res = 0;
    for (int v : e[u])
        res = max(res, f(v));
    return res + a[u];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int u;
        cin >> u;
        cin >> a[u];
        while (1)
        {
            int v;
            cin >> v;
            if (v == 0)
                break;
            //先做 v 才能做 u
            e[v].push_back(u);
        }
    }
    cout << f(1);
    return 0;
}

记忆化搜索优化

时间不可能为 $0$，所以可以用 $0$ 表示没算过。

int book[MAXN + 5];
int f(int u)
{
    if (book[u] != 0)
        return book[u];
    int res = 0;
    for (int v : e[u])
        res = max(res, f(v));
    return book[u] = res + a[u];
}