题目描述:
有n个任务,第i个任务需要时间xi来完成,并且第i个任务必须在它 “前面的” 某些任务完成之后才能开始。
给你任务信息,问你最短需要多少时间来完成任务。
解题报告:
“前面的”,知道这些任务已经是top排序好的了。
dp[i] = 完成第i个任务时所需的最短的时间。
dp[i] = max(dp[j]) xi, j是需要在它前面完成的任务的序号。
max(dp[i])就是答案。
/* * POJ_1949_1.cpp * * Created on: 2013年12月17日 * Author: Administrator */ #include <iostream> #include <cstdio> using namespace std; const int maxn = 10005; int dp[maxn]; void read(){ int n,i,j,k; scanf("%d",&n); int ans = 0; for(i = 1 ; i<= n ; ++i){ scanf("%d%d",&j,&k); int s,t; int p = 0; for(s = 1 ; s <= k ; ++s){ scanf("%d",&t); p = max(dp[t],p); } dp[i] = p+j; ans = max(dp[i],ans); } cout<<ans<<endl; } int main(){ read(); return 0; }