我一直在努力解决我在下面提到的这个问题.我有一些想法,我尝试过.我首先选择了N个元组的所有组合并对它们进行排序,但实现起来很难看而且速度很慢.我认为这个问题有一种动态的编程方法.我在如何创建配置方面遇到了麻烦.在那之后,我想我知道如何解决这个问题.
问题陈述:
给定高度H(1 <= H <= 1,000,000,000),我们需要从N个元组中找到一个大于或等于H的高度序列.有几个条件:N个元组中的每一个都有一个权重,高度,和力量.元组的强度表示可以在该元组之上的最大总权重.
问题要求找到堆栈的最大安全值.安全值是可以在不超过任何较低元组强度的情况下添加的重量.如果不可能,只需打印-1.
INPUT:
第一行输入包含N和H.
接下来的N行输入描述了一个元组,给出了它的高度,重量和强度.所有都是正整数,最多10亿.
样品输入:
4 10
9 4 1
3 3 5
5 5 10
4 4 5
样本输出:
2