一、编程题
1、怪盗基德的滑翔翼
怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。
有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。
假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部（包含初始时的建筑）？
时间限制：1000
内存限制：65536
输入
输入数据第一行是一个整数K（K < 100），代表有K组测试数据。 每组测试数据包含两行：第一行是一个整数N(N < 100)，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h（0 < h < 10000），按照建筑的排列顺序给出。
输出
对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。
样例输入
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10
样例输出
6
6
9
参考答案：
无
解析：【喵呜刷题小喵解析】这个问题可以通过动态规划（Dynamic Programming）解决。动态规划是一种将问题分解为子问题的数学优化技术，常常用于解决最优化问题。在这个问题中，动态规划可以用来计算怪盗基德最多可以经过的建筑数量。我们可以定义一个dp数组，其中dp[i]表示怪盗基德从第i幢建筑开始，最多可以经过的建筑数量。初始化时，dp[0] = 1，表示从任何一幢建筑开始，怪盗基德至少可以经过一幢建筑。然后，我们可以遍历每一幢建筑，对于每一幢建筑，我们遍历它之前的所有建筑，如果当前建筑的高度大于之前建筑的高度，那么怪盗基德可以从之前建筑滑翔到当前建筑，因此我们可以更新dp[i]为dp[j] + 1，其中j是之前建筑的索引。最后，dp数组中的最后一个元素dp[-1]就是怪盗基德最多可以经过的建筑数量。以上算法的时间复杂度为O(N^2)，其中N是建筑的数量。在Python中，我们使用了map函数将输入的字符串转换为整数，并使用for循环遍历每一组测试数据。对于每一组测试数据，我们首先读取建筑的数量和高度，然后计算怪盗基德最多可以经过的建筑数量，并将结果输出到标准输出。
2、数字组合
有n个正整数，找出其中和为t(t也是正整数)的可能的组合方式。如： n=5,5个数分别为1,2,3,4,5，t=5； 那么可能的组合有5=1+4和5=2+3和5=5三种组合方式。
时间限制：1000
内存限制：65536
输入
输入的第一行是两个正整数n和t，用空格隔开，其中1<=n<=20,表示正整数的个数，t为要求的和(1<=t<=1000) 接下来的一行是n个正整数，用空格隔开。
输出
和为t的不同的组合方式的数目。
样例输入
5 5
1 2 3 4 5
样例输出
3
参考答案：
无
解析：【喵呜刷题小喵解析】这是一个动态规划问题。我们使用动态规划来解决它。我们定义`dp[i]`表示和为`i`的组合数目。我们遍历所有数，并计算每个`dp[j]`的值。具体地，我们更新`dp[j]`为`dp[j]`和`dp[j - nums[i]]`之和，其中`nums[i]`是当前遍历到的数。输入包括两个整数`n`和`t`，表示有`n`个正整数，我们要找到它们的和为`t`的组合数目。然后，我们输入`n`个正整数。我们调用`count_combinations`函数来计算和为`t`的组合数目，并输出结果。动态规划的时间复杂度是O(nt)，空间复杂度是O(t)。在这个问题中，n和t的最大值分别是20和1000，所以时间复杂度和空间复杂度都在可接受的范围内。
3、带通配符的字符串匹配
通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等，其中，"?“可以代替一个字符，而”*"可以代替零个或多个字符。
你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。
例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456；
2*77?8可以匹配 24457798、237708、27798。
时间限制：1000
内存限制：65536
输入
输入有两行，每行为一个不超过20个字符的字符串，第一行带通配符，第二行不带通配符
输出
如果两者可以匹配，就输出"matched"，否则输出"not matched"
样例输入
1*456?
11111114567
样例输出
matched
参考答案：
无
解析：【喵呜刷题小喵解析】这是一个字符串匹配的问题，需要判断带通配符的字符串是否能匹配另一个不带通配符的字符串。通配符有问号和星号，问号可以匹配任意单个字符，星号可以匹配任意数量的字符（包括零个）。我们可以使用动态规划来解决这个问题。首先，我们创建一个二维数组dp，dp[i][j]表示pattern的前i个字符是否能匹配text的前j个字符。然后，我们遍历pattern和text的每个字符，根据当前字符和通配符的类型来更新dp数组。具体地，如果当前字符匹配，那么dp[i][j] = dp[i-1][j-1]；如果当前字符是星号，那么dp[i][j] = dp[i-1][j] or dp[i][j-1]。最后，如果dp[m][n]为True，表示两个字符串可以匹配，否则表示不能匹配。在Python中，我们可以使用strip()函数来去除字符串两端的空格，然后使用if-elif-else语句来根据当前字符和通配符的类型来更新dp数组。最后，我们输出匹配的结果。
4、股票买卖
最近越来越多的人都投身股市，阿福也有点心动了。谨记着"股市有风险，入市需谨慎"，阿福决定先来研究一下简化版的股票买卖问题。
假设阿福已经准确预测出了某只股票在未来 N 天的价格，他希望买卖两次，使得获得的利润最高。为了计算简单起见，利润的计算方式为卖出的价格减去买入的价格。
同一天可以进行多次买卖。但是在第一次买入之后，必须要先卖出，然后才可以第二次买入。
现在，阿福想知道他最多可以获得多少利润。
时间限制：1000
内存限制：65536
输入
输入的第一行是一个整数 T (T <= 50) ，表示一共有 T 组数据。 接下来的每组数据，第一行是一个整数 N (1 <= N <= 100, 000) ，表示一共有 N 天。第二行是 N 个被空格分开的整数，表示每天该股票的价格。该股票每天的价格的绝对值均不会超过 1,000,000 。
输出
对于每组数据，输出一行。该行包含一个整数，表示阿福能够获得的最大的利润。
样例输入
3
7
5 14 -2 4 9 3 17
6
6 8 7 4 1 -2
4
18 9 5 2
样例输出
28
2
0
提示
对于第一组样例，阿福可以第 1 次在第 1 天买入（价格为 5 ），然后在第 2 天卖出（价格为 14 ）。第 2 次在第 3 天买入（价格为 -2 ），然后在第 7 天卖出（价格为 17 ）。一共获得的利润是 (14 - 5) + (17 - (-2)) = 28 对于第二组样例，阿福可以第 1 次在第 1 天买入（价格为 6 ），然后在第 2 天卖出（价格为 8 ）。第 2 次仍然在第 2 天买入，然后在第 2 天卖出。一共获得的利润是 8 - 6 = 2 对于第三组样例，由于价格一直在下跌，阿福可以随便选择一天买入之后迅速卖出。获得的最大利润为 0
参考答案：
无
解析：【喵呜刷题小喵解析】这道题是一道经典的动态规划问题，可以使用动态规划来解决。由于题目要求先买入再卖出，所以我们只需要考虑买入的价格小于当前价格的情况。同时，由于同一天可以进行多次买卖，所以我们可以在第j天买入，然后在第i天卖出，其中j < i。在遍历价格数组时，我们可以使用动态规划的思想，定义一个dp数组，其中dp[i]表示在第i天卖出股票时能够获得的最大利润。然后，我们遍历j，其中j < i，计算dp[i] = max(dp[i], prices[i] - prices[j])，更新dp数组。最终的最大利润即为dp数组中的最大值。需要注意的是，由于价格数组的长度可能很大，我们需要使用一种高效的方法来更新dp数组。一种常用的方法是使用单调队列来维护一个递减的序列，从而避免重复计算。具体实现时，我们可以使用一个双端队列来存储下标，队列中的下标对应的价格是一个递减的序列。在遍历价格数组时，我们不断将队首元素出队，直到队列为空或者队列队首元素对应的价格大于等于当前价格。然后，我们将当前价格与队尾元素对应的价格相减，并将结果更新到dp数组中。同时，我们需要将队列中价格小于当前价格的下标出队，保证队列中价格的递减性。最后，我们将当前下标入队，继续遍历下一个价格。最终的最大利润即为dp数组中的最大值。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
