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;
}
};