(POJ DP1.1)POJ 1949 Chores(简单DP)

题目描述：

有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 
  
   
#include  
   
     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<