青少年软件编程（C语言）等级考试试卷（四级）
分数：100 题数：4
一、编程题(共4题，共100分)
1.
最长上升子序列
试题编号：20200621-401
试题类型：编程题
标准答案：
试题难度：一般
2.
核电站
试题编号：20200621-403
试题类型：编程题
标准答案：
试题难度：一般
3.
山区建小学
试题编号：20200621-404
试题类型：编程题
标准答案：
试题难度：一般
4.
公共子序列
试题编号：20200621-402
试题类型：编程题
标准答案：
试题难度：一般
试题解析：
最长上升子序列
一个数的序列
b
i
，当
b
1
<
b
2
< ... <
b
S
的时候，我们称这个序列是上升的。对于给定的一个序列(
a
1
,
a
2
, ...,
a
N
)，我们可以得到一些上升的子序列(
a
i1
,
a
i2
, ...,
a
iK
)，这里1 <=
i
1
<
i
2
< ... <
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。
输出
最长上升子序列的长度。
样例输入
7
1 7 3 5 9 4 8
样例输出
4
核电站
一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
时间限制：6000
内存限制：131072
输入
只一行，两个正整数N，M( 1 < N < 50，2 ≤ M ≤ 5 )
输出
一个正整数S，表示方案总数。
样例输入
4 3
样例输出
13
山区建小学
政府在某山区修建了一条道路，恰好穿越总共m个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为di（为正整数），其中，0 < i < m。为了提高山区的文化素质，政府又决定从m个村中选择n个村建小学（设 0 < n < = m < 500 ）。请根据给定的m、n以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
时间限制：24000
内存限制：65536
输入
第1行为m和n，其间用空格间隔 第2行为(m-1) 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。 例如 10 3 2 4 6 5 2 4 3 1 3 表示在10个村庄建3所学校。第1个村庄与第2
202006软件编程（C语言）真题——（4级）