Mice and CheeseThere are two mice and n different types of cheese each type of cheese should be eaten by exactly one mouseA point of the cheese with index i 0-indexed isreward1i if the first mouse eat

One approach to solve this problem is to use dynamic programming. We can define dp[i][j] as the maximum points that can be achieved if the first mouse eats i types of cheese and the second mouse eats j types of cheese.

To compute dp[i][j], we can iterate over all possible types of cheese that the first mouse can eat (from the remaining ones that the second mouse hasn't eaten yet), and add the corresponding reward to dp[i][j]. Similarly, we can iterate over all possible types of cheese that the second mouse can eat (from the remaining ones that the first mouse hasn't eaten yet), and add the corresponding reward to dp[i][j]. We take the maximum value between these two options.

The base case is dp[0][0] = 0, since both mice are not eating any cheese.

Finally, the answer is dp[k][n-k], since the first mouse has eaten k types of cheese, and the second mouse has eaten n-k types of cheese.

Here is the C++ code:

int miceAndCheese(vector& reward1, vector& reward2, int k) { int n = reward1.size(); vector<vector> dp(k+1, vector(n-k+1, 0)); for (int i = 1; i <= k; i++) { for (int j = 1; j <= n-k; j++) { for (int l = 0; l < n; l++) { if (l < i) { dp[i][j] = max(dp[i][j], reward1[l] + dp[i-1][j]); } else { dp[i][j] = max(dp[i][j], reward2[l] + dp[i][j-1]); } } } } return dp[k][n-k]; }