1626.无矛盾的最佳球队

1626.无矛盾的最佳球队题目描述：一支球队，长度为 n ，每个球员有 score[i],age[i] 。如果年龄较小的球员的分数严格大于一名年龄较大的球员，则存在矛盾。同龄没有矛盾。返回可能的无矛盾球队中得分最高的分数。数据范围： 1\le n \le 1000,1\le scores[i] \le 10^6,1\le ages[i] \le 1000 题解：很容易想到使用动态规划解决，设计状态 dp[i] 表示选择 i 号球员时能得到的最大分数。首先排序，按照年龄或者按照分数（这里先按照年龄排序）。这样的话可以得到递推方程dp[i] =\begin{cases} max(dp[i], dp[j] + score[i]),&j < i \and scores[i] >= scores[j]\\ scores[i], &otherwise\end{cases}可以发现 dp[i] 的值只与当前值和 [0, scores[i]] 区间中分数的最大值有关。所以可以使用序列数据结构维护该区间最值（使用线段树或者树状数组）。由于 scores 的数据范围大一些，所以可以考虑维护 age 。也可...

Submit