问题 23779 --圣诞树

23779: 圣诞树

时间限制: 1 Sec  内存限制: 128 MB
提交: 112  解决: 33
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][104kb]

题目描述

圣诞特别礼物挂在一棵圣诞树上,这棵树有n层,每层有一件礼物,每件礼物都有一个价值,有的礼物还有一些连结线,与下层的礼物相连,领取礼物的规则如下:任选一件礼物,它的下面如果有连结线,则可以继续取它连结的礼物,以此类推,直至取到没有连结线的礼物才结束,你如果是第一个去取,怎样取才能获得最大的价值呢?请你编一程序解决这一问题。

输入

输入文件tree.in的第一行只有一个数据n(n<=100),表示有n层礼物,以下有n行数据,分别表示第1-n层礼物的状态,每行至少由一个数据构成,且第一个数据表示该礼物的价值,后面的数据表示它与哪些层的礼物相连,如果每行只有一个数据则说明这层礼物没有与下层礼物相连,每个数的大小均不超过10000

输出

输出文件tree.out也只有一个数,表示获得的取大价值。

样例输入

3
12 2 3
20
30

样例输出

42

提示

来源

[提交][状态]