子序列的最大优雅度

给你一个长度为 n 的二维整数数组 items 和一个整数 k 。
items[i] = [profiti, categoryi]，其中 profiti 和 categoryi 分别表示第 i 个项目的利润和类别
现定义 items 的 子序列的优雅度 可以用 total_profit + distinct_categories2 计算
从 items 所有长度为 k 的子序列中，找出最大优雅度

1. 反悔贪心

结果的值受利润和种类两个维度影响，我们可以先考虑一个维度，然后再对另一个维度进行贪心替换
先按利润从大到小排序，贪心取前k个值，并且记录类别和重复类别的利润
后面对可以增加种类的值进行替换，并且动态规划记录更新当下最大值

class Solution {
public:
    long long findMaximumElegance(vector<vector<int>>& items, int k) {
        //只能遍历一次，要么贪心、要么排序贪心
        int n = items.size();
        long long res = 0;
        long long total = 0;
        //先按利润从大到小排序
        sort(items.begin(), items.end(), [](const auto &a, const auto &b) {
            return a[0] > b[0];
        });
        unordered_set<int> vis;
        stack<int> duplicate;//重复类别的利润
        for(int i=0;i<n;i++){ //只需遍历一次
            int profit = items[i][0]; int category = items[i][1];
            if(i<k){//先贪心选中前k个
                total += profit;//计算总利润
                if(vis.count(category))
                    duplicate.push(profit);//非第一个的重复类别利润，后面用作替换
                vis.insert(category);
            }
            else if(!duplicate.empty()&&!vis.count(category)){//对于候选替换数，如果存在可替换的重复类别，且当前类别没出现过
                //进行替换
                vis.insert(category);
                total += profit - duplicate.top();
                duplicate.pop();
            }
            //动态规划，记录最大值
            res = max(res, total + (long long)vis.size()*(long long)vis.size());
        }
        return res;
    }
};