一、编程题
1、开餐馆
北大信息学院的同学小明毕业之后打算创业开餐馆.
现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。
这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, ... mn 来表示他们的相对位置。
由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。
请你帮助小明选择一个总利润最大的方案。
时间限制：1000
内存限制：65536
参考答案：
略
解析：【喵呜刷题小喵解析】：这个问题可以使用动态规划来解决。首先，我们需要定义一个数组dp，其中dp[i]表示在前i个地点开设餐馆的最大利润。然后，我们可以使用两层循环来遍历所有可能的餐馆开设方案。外层循环遍历所有的地点，内层循环遍历所有可能的起始地点。在内层循环中，我们需要判断当前地点和起始地点之间的距离是否大于k，如果是，则更新dp[i]为dp[j] + p[i]，其中j表示起始地点。最后，返回dp[n]即可，其中n表示地点的数量。注意，由于题目中要求餐馆之间的距离必须大于k，因此在内层循环中需要判断m[i - 1] - m[j - 1] > k。以上代码实现了上述思路，其中n、k、p和m分别表示地点的数量、餐馆之间的距离限制、每个地点的利润和每个地点的位置。
2、邮票收集
小A是个邮票收集爱好家，他有n种面值的邮票，每种邮票都有无数张。
一天小B想要寄信，需要一共面值和为k的邮票组合。
小A想要知道拼出面值为k的邮票最少需要多少张。
时间限制：1000
内存限制：131072
参考答案：
略
解析：【喵呜刷题小喵解析】：这个问题可以通过动态规划解决。定义dp[i]为拼出面值为i的邮票所需的最少邮票数量。初始时，dp[0] = 0，因为不需要邮票就能拼出0面值的邮票。对于每一种面值的邮票，我们都考虑从1到该面值的所有可能的和，对于每一种和j，我们都计算使用当前邮票和已有的邮票（即j-i）来拼出j所需的邮票数量，取最小值作为dp[j]的值。最后，dp[k]即为所求。注意，这个问题的时间复杂度为O(n*k)，其中n为邮票的面值种类数，k为需要拼出的邮票面值。在题目给定的时间限制和内存限制下，这个算法是可以接受的。
3、带通配符的字符串匹配
通配符是一类键盘字符，当我们不知道真正字符或者不想键入完整名字时，常常使用通配符代替一个或多个真正字符。
通配符有问号(?)和星号(*)等，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。
你的任务是，给出一个带有通配符的字符串和一个不带通配符的字符串，判断他们是否能够匹配。
例如，1?456 可以匹配 12456、13456、1a456，但是却不能够匹配23456、1aa456；
2*77?8可以匹配 24457798、237708、27798。
时间限制：1000
内存限制：65536
参考答案：
略
解析：【喵呜刷题小喵解析】：这个问题是一个经典的动态规划问题，可以通过使用动态规划算法来解决。我们可以创建一个二维的布尔矩阵，其中 dp[i][j] 表示 pattern 的前 i 个字符是否能够匹配 text 的前 j 个字符。首先，我们初始化 dp[0][0] 为 True，因为空字符串可以匹配空字符串。然后，我们遍历 pattern 的每个字符。如果当前字符是星号（*），那么 pattern 的前 i 个字符可以匹配 text 的前 0 个字符，即 dp[i][0] = dp[i-1][0]。最后，我们遍历 pattern 的每个字符和 text 的每个字符。如果当前字符相等或者当前字符是问号（?），那么 pattern 的前 i 个字符可以匹配 text 的前 j 个字符，即 dp[i][j] = dp[i-1][j-1]。如果当前字符是星号（*），那么 pattern 的前 i 个字符可以匹配 text 的前 j 个字符，当且仅当 pattern 的前 i-1 个字符可以匹配 text 的前 j 个字符，或者 pattern 的前 i 个字符可以匹配 text 的前 j-1 个字符，即 dp[i][j] = dp[i-1][j] or dp[i][j-1]。最后，返回 dp[m][n]，其中 m 是 pattern 的长度，n 是 text 的长度。如果 dp[m][n] 为 True，那么 pattern 可以匹配 text，否则不能匹配。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
