首页 > 代码库 > [洛谷P1113]杂务
[洛谷P1113]杂务
题目大意：有一些工作，每项工作有一个时间，有些工作要在一些其他工作完成的情况下才能做。如果两项工作没有冲突，即可同时进行。求完成工作的最短时间。
解题思路：DP。我们设f[i]为工作i的最短完成时间（包括完成准备工作的时间）,则f[i]=max(f[i的准备工作])+工作i所花的时间。因为题目说，第k个任务的准备工作只可能在1..k-1中，而求f[k]时，f[1..k-1]已经求出值了，所以并不需要什么拓扑排序。最后答案为f中的最大值。
C++ Code：
#include<bits/stdc++.h>using namespace std;int n;int f[10005];int main(){ scanf("%d",&n); for(int i=1;i<=n;++i){ int x,t,Max=0; scanf("%d",&x); scanf("%d%d",&x,&t); while(t){ Max=max(Max,f[t]); scanf("%d",&t); } f[i]=Max+x; } printf("%d\n",*max_element(f+1,f+n+1)); return 0;}
[洛谷P1113]杂务
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。