nowcoder multi 4A

题目大意

给定一个序列 ，有两个属性 和 ，从中选出 个元素，最大化

解题方法

首先考虑一个简化版问题，如果 ，那么问题就会转化为指定一个顺序，让答案最大。我们对这种情况考虑贪心。假设s位置与t位置互换，对答案的贡献为

当 时，问题简化为求。

因此我们可以看出，如果要使答案最大，必定要使该表达式大于0。由答案的传递性可知，可以以此作为排序的依据，得到一个有序的序列。

接下来考虑 的情况。这种情况，相当于从序列中选择出 个数使答案最大。这是因为我们可以保证每个选出的序列都必须按照在本序列中的顺序排序。动态规划的思路非常显然。我们按从大到小的顺序来做， 。