一、编程题
1、最长上升子序列（2024.3四级）
一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)，我们可以得到一些上升的子序列(ai1, ai2, …, aiK)，这里1 <= i1 < i2 < … < iK <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。
时间限制：11000
内存限制：65536
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7 1 7 3 5 9 4 8
样例输出
4
参考答案：对于给定的序列，最长上升子序列的长度为4。
解析：【喵呜刷题小喵解析】：
这个问题是一个经典的动态规划问题，可以通过动态规划算法来解决。
首先，我们需要定义一个数组dp，其中dp[i]表示以第i个数结尾的最长上升子序列的长度。初始时，所有的dp值都为1，因为每个数本身都可以构成一个长度为1的上升子序列。
然后，我们遍历序列中的每个数，对于每个数a[i]，我们再遍历它之前的所有数a[j]，其中j的取值范围是1到i-1。如果a[j] < a[i]，说明我们可以将a[i]加入到以a[j]结尾的上升子序列中，形成一个更长的上升子序列。因此，我们可以更新dp[i]的值为dp[i]和dp[j]+1中的较大值。
最后，我们遍历dp数组，找到其中的最大值，即为最长上升子序列的长度。
对于样例输入，我们可以按照上述算法进行计算，得到最长上升子序列的长度为4。
2、重启系统（2024.3四级）
小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？
时间限制：1000
内存限制：65536
输入
第一行： N (2 <= N <= 1000) 待处理的任务数 第二行： N个整数，每个任务的数据量
输出
输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示
回想一下最长上升子序列问题
参考答案：要完成最多任务，我们可以采用动态规划的方法来解决这个问题。我们可以定义一个dp数组，其中dp[i]表示以第i个任务为结尾的最长上升子序列的长度。初始化dp数组为1，表示每个任务本身都可以作为一个上升子序列。然后，我们遍历从1到N的任务，对于每个任务i，我们遍历之前的任务j，如果j < i且任务j的数据量小于任务i的数据量，那么我们可以将任务i加入到以任务j为结尾的上升子序列中，更新dp[i]为dp[j]+1。最后，我们找到dp数组中的最大值，即为最多能完成的任务数。
解析：【喵呜刷题小喵解析】：
这个问题实际上是一个最长上升子序列问题，但是增加了限制条件：系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。这意味着我们不能随意地选择任务来形成上升子序列，而是需要保证每次选择的任务的数据量不超过前一个任务的数据量。
为了解决这个问题，我们可以采用动态规划的方法。首先，我们定义一个dp数组，其中dp[i]表示以第i个任务为结尾的最长上升子序列的长度。然后，我们遍历从1到N的任务，对于每个任务i，我们遍历之前的任务j，如果j < i且任务j的数据量小于任务i的数据量，那么我们可以将任务i加入到以任务j为结尾的上升子序列中，更新dp[i]为dp[j]+1。
最后，我们找到dp数组中的最大值，即为最多能完成的任务数。这个最大值就是最长上升子序列的长度，满足题目中的限制条件。
在样例输入中，任务的数据量为1 5 4 3 2 10 9 8 7 6，我们可以得到的最长上升子序列为1 3 4 6 7 8 9，共7个任务。但是，由于题目中限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量，所以我们需要重新考虑任务的选择。我们可以选择的任务为1 3 4 5 6 9 10，共7个任务，这也是满足限制条件的最长上升子序列。但是，如果我们使用一次重启系统，我们可以将系统恢复到最高性能，从而可以处理更大的数据量。在这种情况下，我们可以选择的任务为1 3 4 5 6 7 8 9 10，共10个任务，这就是最多能完成的任务数。
因此，对于样例输入，最多能完成的任务数为9。
3、硬币（2024.3四级）
宇航员 Bob 有一天来到火星上， 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了， 一共有 n 种， 每种只有一个： 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物， 想买来送给朋友 Alice， 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的， 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零， 只接受恰好 X 元。
时间限制： 1000
内存限制： 262144
输入
第一行包含两个正整数 n 和 x。 （1 <= n <= 200, 1 <= x <= 10000)
第二行从小到大为 n 个正整数 a1, a2, a3 … an （1 <= ai <= 10000)
输出
第一行是一个整数， 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值（从小到大排列） 。
样例输入
5 18 1 2 3 5 10
样例输出
2 5 10
提示
输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币， 则第一行输出 0， 第二行输出空行。
参考答案：1. 读取输入，获取硬币的面值和礼物的价格。2. 从面值最大的硬币开始，逐步尝试使用硬币组合支付礼物价格。3. 如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。4. 如果无法恰好支付礼物价格，则尝试使用下一个面值的硬币。5. 输出必须使用的硬币种类和数量。
解析：【喵呜刷题小喵解析】：
本题是一道典型的贪心算法问题，要求找出能够恰好支付礼物价格的硬币组合。由于硬币的面值已经按照从小到大的顺序给出，因此我们可以从面值最大的硬币开始，逐步尝试使用硬币组合支付礼物价格。
具体的算法如下：
1. 从面值最大的硬币开始，依次尝试将其加入当前硬币组合中，判断当前硬币组合是否能够恰好支付礼物价格。
2. 如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。
3. 如果无法恰好支付礼物价格，则尝试使用下一个面值的硬币，重复步骤1和2。
4. 如果所有硬币都无法恰好支付礼物价格，则说明不存在必须使用的硬币，输出0和空行。
在算法实现中，我们可以使用一个变量记录当前硬币组合的面值总和，初始值为0。然后，从面值最大的硬币开始，依次将其加入当前硬币组合中，更新硬币组合的面值总和。如果当前硬币组合能够恰好支付礼物价格，则记录必须使用的硬币种类，并结束循环。如果无法恰好支付礼物价格，则继续尝试下一个面值的硬币。
需要注意的是，由于硬币的面值已经按照从小到大的顺序给出，因此我们可以直接使用贪心算法来解决问题。如果硬币的面值不是按照从小到大的顺序给出，则需要进行排序操作，否则可能会导致算法出错。
4、奶牛散步
从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
时间限制：10000
内存限制：131072
输入
一个数字，代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
参考答案：对于样例输入2，输出结果为7。
解析：【喵呜刷题小喵解析】：
这个问题是一个经典的动态规划问题，可以使用动态规划算法来解决。
首先，定义一个二维数组dp[i][j]，其中dp[i][j]表示从中心点出发，走了i步到达位置(i,j)的方案数。
由于一步只能向右走、向上走或向左走，因此状态转移方程为：
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i+1][j]
但是需要注意的是，由于不能经过已走的点，因此需要排除一些无效的状态。
对于dp[i][j]，如果它已经被访问过，那么就不能将其纳入状态转移方程中。
因此，需要在遍历的过程中，记录已经访问过的点，并在状态转移方程中进行排除。
最后，遍历所有可能的步数，求出总的方案数即可。
在遍历的过程中，需要注意模运算，以避免整数溢出。
最后，将总的方案数对12345取模，即可得到最终的结果。
对于样例输入2，可以计算出总的方案数为7。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
