苹果消消乐有100个苹果和香蕉排成一条直线，其中有N个香蕉，你可以使用至多M次魔法道具将香蕉变成苹

苹果消消乐
有100个苹果和香蕉排成一条直线，其中有N个香蕉，你可以使用至多M次魔法道具将香蕉变成苹果，最后"最长的连续苹果数量"即为你本次苹果消消乐的得分，给定苹果和香蕉的排列，求你能获得的最大得分。
时间限制：1000
内存限制：65536
输入
第一行是一个整数T(1 <= T <= 10)，代表测试数据的组数。每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, … aN(1 <= a1 < a2 < … < aN <= 100)，表示第a1, a2, … aN个位置上摆放的是香蕉。
输出
对于每组数据，输出通过使用魔法道具后你能获得的最大得分。
样例输入

3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90

样例输出

76
59
100

提示
这是个枚举题

解析：

【喵呜刷题小喵解析】本题是一个动态规划的问题，需要求出通过使用魔法道具后能够获得的最大得分。我们可以定义一个二维数组dp，其中dp[i][j]表示前i个位置，且使用了j次魔法道具能够获得的最大得分。对于每个位置i，我们有两种选择：1. 不使用魔法道具，即dp[i][j] = dp[i-1][j]；2. 使用魔法道具将第i个位置的香蕉变成苹果，即dp[i][j] = dp[k][j-1] + (i - k)，其中k是上一个香蕉的位置。因此，我们需要遍历所有的位置i，对于每个位置i，我们再遍历它之前的所有位置k，找出上一个香蕉的位置，并比较两种选择中较大的那个，即为dp[i][j]的值。最终，dp[100][M]即为所求的最大得分。具体的实现中，我们还需要考虑一个细节：如果某个位置i是一个香蕉，且我们没有魔法道具可以使用，那么dp[i][0]应该为0，因为无法将香蕉变成苹果。根据题目中的输入样例，我们可以写出如下的代码：```pythonT = int(input())for _ in range(T):N, M = map(int, input().split())a = list(map(int, input().split()))dp = [[0] * (M + 1) for _ in range(N + 1)]for i in range(1, N + 1):if a[i - 1] == 1:dp[i][0] = 1for j in range(1, M + 1):dp[i][j] = dp[i - 1][j]for k in range(i - 1, i - len(a) - 1, -1):if a[k] == i:dp[i][j] = max(dp[i][j], dp[k][j - 1] + (i - k))print(dp[N][M])```时间复杂度为O(N^2 * M)，空间复杂度为O(N * M)，满足题目要求。

答案：

解析：

最热门资讯

JAVA工程师面试指导--猎头内部资料

常见面试问题100问！