青少年软件编程（C/C++）4级等级考试真题试卷（2024年3月）

最长上升子序列（2024.3四级）

一个数的序列b_i，当b₁ < b₂ < … < b_S的时候，我们称这个序列是上升的。对于给定的一个序列(a₁, a₂, …, a_N)，我们可以得到一些上升的子序列(a_i1, a_i2, …, a_iK)，这里1 <= i₁ < i₂ < … < i_K <= 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。

输出

最长上升子序列的长度。

样例输入

71 7 3 5 9 4 8

样例输出

4

重启系统（2024.3四级）

小明帮助管理一个处理数据的计算系统，有N个待处理的任务，需要按照顺序来完成这些任务，即每次所完成任务的编号都要大于前一个完成任务的编号，且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序，它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能（一开始系统拥有最高性能，最高性能大于任何待处理任务的数据量）。小明有一次重启系统的权限（也可以不使用），你能帮他算出最多能完成几个任务吗？

时间限制：1000

内存限制：65536

输入

第一行： N (2 <= N <= 1000) 待处理的任务数 第二行： N个整数，每个任务的数据量

输出

输出只包括一行，这一行只包含一个整数，表示最多能完成的任务数。

样例输入

10

1 5 4 3 2 10 9 8 7 6

样例输出

9

提示

回想一下最长上升子序列问题

硬币（2024.3四级）

宇航员 Bob 有一天来到火星上， 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了， 一共有 n 种， 每种只有一个： 面值分别为 a₁,a₂… a_n。 Bob 在机场看到了一个特别喜欢的礼物， 想买来送给朋友 Alice， 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的， 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零， 只接受恰好 X 元。

时间限制： 1000

内存限制： 262144

输入

第一行包含两个正整数 n 和 x。 （1 <= n <= 200, 1 <= x <= 10000)

第二行从小到大为 n 个正整数 a₁, a₂, a₃ … a_n （1 <= a_i <= 10000)

输出

第一行是一个整数， 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值（从小到大排列） 。

样例输入

5 181 2 3 5 10

样例输出

25 10

提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币， 则第一行输出 0， 第二行输出空行。

奶牛散步

从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

时间限制：10000

内存限制：131072

输入

一个数字，代表N,N<=1000

输出

输出有多少方案数模12345

样例输入

2

样例输出

7