技能树最优学习路径
解题思路
题目要求选择一条学习路径。由于每个技能最多只有 1 个直接前置技能,且依赖关系无环,所以所有技能会形成若干棵树。
对于一条合法学习路径:
题目内容
你正在玩一款游戏,游戏中有一个技能树系统。每个技能都有:
- 学习所需的时间成本(小时)
- 提升的战斗力(无重复)
- 前置技能(必须先学习的技能)
你有有限的总学习时间 T ,需要在技能树中选择一条最优的学习路径,使得在时间限制内获得最大总战斗力。
输入描述
第一行:两个整数 N 和 T
- N :技能数量( 1 ≤ N ≤ 100 )
- T :总可用时间( 1 ≤ T ≤ 1000 )
接下来 N 行:每行描述一个技能(各字段之间以空格分隔)
- 技能编号: 1 到 N
- time :学习时间( 1 ≤ time ≤ 100 )
- power :提升的战斗力值( 1 ≤ power ≤ 1000 )
- k :前置技能数量( 0 ≤ k ≤ 1 )
- 前置技能编号(如果有)
输出描述
输出一个整数:在时间 T 内能获得的最大战斗力。
如果在时间 T 内无法完成任意一个技能(例如 T = 1 ,任意一个技能学习时间均大于 1 ),则输出 0 。
样例1
输入
2 1
1 2 15 0
2 4 20 0
输出
0
说明
学习技能 1 、 2 所需要的时间均大于总学习时间 1 ,无法完成任意技能的学习,因此输出 0 。
样例2
输入
4 8
1 3 25 0
2 4 30 0
3 5 40 1 1
4 2 20 1 2
输出
65
说明
- 学习技能 1 ( 3 h, 25 p) + 技能 3 ( 5 h, 40 p) = 8 h,总战斗力 65 ;
- 学习技能 1 ( 3 h, 25 p) + 技能 4 ( 2 h, 20 p) = 7 h,总战斗力 55 ;
- 学习技能 2 ( 4 h, 30 p) + 技能 4 ( 2 h, 20 p) = 6 h,总战斗力 50 ;
最终得到的最大总战斗力为 65 。
提示
- 每个技能只列出其直接前置技能。
- 每个技能最多只有 1 个直接前置技能( k ≤ 1 ),且输入保证依赖关系不形成环。