2611. 老鼠和奶酪

有两只老鼠和 n 块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。

下标为 i 处的奶酪被吃掉的得分为：

如果第一只老鼠吃掉，则得分为 reward1[i] 。
如果第二只老鼠吃掉，则得分为 reward2[i] 。
给你一个正整数数组 reward1 ，一个正整数数组 reward2 ，和一个非负整数 k 。

请你返回第一只老鼠恰好吃掉 k 块奶酪的情况下，最大 得分为多少。

示例 1：

输入：reward1 = [1,1,3,4], reward2 = [4,4,1,1], k = 2
输出：15
解释：这个例子中，第一只老鼠吃掉第 2 和 3 块奶酪（下标从 0 开始），第二只老鼠吃掉第 0 和 1 块奶酪。
总得分为 4 + 4 + 3 + 4 = 15 。
15 是最高得分。
示例 2：

输入：reward1 = [1,1], reward2 = [1,1], k = 2
输出：2
解释：这个例子中，第一只老鼠吃掉第 0 和 1 块奶酪（下标从 0 开始），第二只老鼠不吃任何奶酪。
总得分为 1 + 1 = 2 。
2 是最高得分。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/mice-and-cheese
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

DFS（503/564）

class Solution {
public:
    int res=0;
    void dfs(vector<int>reward1,vector<int>reward2,int k,int eat1,int poi,int now){
        if(eat1>k)  return;
        if(poi>=reward1.size()){
            if(eat1==k)
                res=max(res,now);
            return;
        }
        dfs(reward1,reward2,k,eat1+1,poi+1,now+reward1[poi]);
        dfs(reward1,reward2,k,eat1,poi+1,now+reward2[poi]);
    }


    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        dfs(reward1,reward2,k,0,0,0);
        return res;
    }
};

[54,59,94,87,32,10,55,44,21,73,12,70,89,49,13,34,78,20,20,75,90,44,48,74,78,32,70,76,79,49,50,69]
[78,43,69,22,32,67,65,38,51,4,21,27,82,61,12,85,62,60,67,16,22,3,5,16,13,35,13,41,72,85,20,54]
17

超出内存限制，看了下题解也没有写dfs的，也懒得去更改递归条件了。

diff+排序

题目可以理解为。用1中的k个数去替换2中的数。使2的和最大。可以先将2的和算出来。然后将差值最大的k个数加上

class Solution {
public:
    int miceAndCheese(vector<int>& reward1, vector<int>& reward2, int k) {
        //若全是第二只老鼠吃的
        int sum=0;
        for(int num:reward2)   sum+=num;
        //计算同一块奶酪由不同老鼠吃的差值
        for(int i=0;i<reward1.size();i++)   reward1[i]-=reward2[i];
        sort(reward1.begin(),reward1.end(),greater<int>());
        for(int i=0;i<k;i++)    sum+=reward1[i];
        return sum;
    }
};