P1113 杂务

https://www.luogu.org/problem/show?pid=1113#sub

（一开始写了拓扑，然而没有考虑周到，全WA，然后发现不好改，弃疗；考虑到问题的特殊性，换了递推）

问题的特殊性：John有需要完成的n个杂务的清单，并且这份清单是有一定顺序的，杂务k(k>1)的准备工作只可能在杂务1..k-1中。
即当前任务的杂务都是前面已经完成的，那么就可以在子杂务里找一个时间最长的，加上当前任务的时间，即完成当前任务的时间

最后在所有任务里找时间最长的即为答案

复制代码#include<iostream> #include<cstring> #include<cstdio> #include<string> #include<cmath> #include<vector> using namespace std; int n,t[10009]; vector <int> k[10009]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); t[x]=y; while(1) { scanf("%d",&x); if(!x) break; k[i].push_back(x); } int p=0; for(int j=0;j<k[i].size();j++) { p=max(p,t[k[i][j]]); } t[i]+=p; } int ans=0; for(int i=1;i<=n;i++) ans=max(ans,t[i]); printf("%d",ans); return 0; }

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
34
35
36
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
int n,t[10009];
vector <int> k[10009];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        t[x]=y;
        while(1)
        {
            scanf("%d",&x);
            if(!x) break;
            k[i].push_back(x);
        }
        int p=0;
        for(int j=0;j<k[i].size();j++)
        {
            p=max(p,t[k[i][j]]);
        }
        t[i]+=p;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    ans=max(ans,t[i]);
    printf("%d",ans);
    return 0; 
}