题目内容

小塔正在给自己的物品贴标签。她一共有$m$种不同的标签，每种标签只有一个。 对于第$i$个物品，如果贴上$a_i$号标签，那么它的美观值为$b_i$;如果没有贴上$a_i$号标签，则其美观值为$c_i$。 小美想知道在合理的分配下，所有物品的美观值之和最大为多少。

输入描述

思路

思路是使用贪心算法。首先，将所有物品按照其适合的标签分类。然后，在每一类标签内，根据物品贴上标签后的美观度增量来排序，具体为 (b[x] - c[x])，即物品贴上适合标签后的美观度与未贴上标签时的美观度差值。为了方便实现降序排序，我们可以使用 (c[x] - b[x]) 进行排序。接下来，在确保美观度最大的情况下，为每类中的美观度增量最大的物品贴上标签，即取 ( \text{max}(b[lst[0]], c[lst[0]]) )。对于同一类中的其他物品，则不贴标签。最后，将每一类中的最大美观度累加起来，即为总的美观值。

代码

python

def max_aesthetic_value(n, m, a, b, c):