【题解】洛谷1113 杂务

本题地址： http://www.luogu.org/problem/show?pid=1113

题目描述

输入输出格式

第1行：一个整数n，必须完成的杂务的数目(3<=n<=10,000)；
第2 ~ n+1行： 共有n行，每行有一些用1个空格隔开的整数，分别表示：
　* 工作序号(1..n,在输入文件中是有序的)；
　* 完成工作所需要的时间len（1<=len<=100）；
　* 一些必须完成的准备工作，总数不超过100个，由一个数字0结束。有些杂务没有需要准备的工作只描述一个单独的0，整个输入文件中不会出现多余的空格。

一个整数，表示完成所有杂务所需的最短时间。

输入输出样例

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

23

模型是图，主要明白题意之后，利用递推的方法，将之前的状态存储到a[f]数组中，没什么难度

附代码

var sum,i,tot,m,n,f,p:longint;

 a:array[0..10000]of longint;

function max(a,b:longint):longint;

 begin

 if a>b then exit(a)

  else exit(b);

 end;

begin

readln(n);

for i:=1 to n do

 begin

 m:=0;

 read(p,tot,f);

 while(f<>0)do

  begin

   m:=max(m,a[f]);

   read(f);

  end;

 readln;

 a[i]:=m+tot;

 sum:=max(a[i],sum);

 end;

write(sum);

end.