电子学会青少年软件编程(C语言四级)等级考试真题试卷(2022年9月)-附完整版720765453.pdf

电子学会青少年软件编程(C语言四级)等级考试真题试卷(2022年9月)-附完整版720765453--第1页

青少年软件编程（C语言四级）等级考试真题试卷（2022年9月）

题目总数：4总分数：100时间：不限时

第1题问答题

最长上升子序列

一个数的序列bi，当b1b2…bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,

aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1=i1i2…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

1735948

样例输出

4

答案#includebits/stdc++.h

usingnamespacestd;

intmain(){

#ifdefLOCAL

freopen(202209_4_1.in,r,stdin);

#endif

intN;

scanf(%d,N);

inta[1010];

for(inti=0;iN;i++){

scanf(%d,a[i]);

电子学会青少年软件编程(C语言四级)等级考试真题试卷(2022年9月)-附完整版720765453--第1页

博学佑航-青少年考级竞赛题库

电子学会青少年软件编程(C语言四级)等级考试真题试卷(2022年9月)-附完整版720765453--第2页

}

//定义dp[i]为以i位结尾的最长上升序列长度

intdp[1010];

dp[0]=1;

intmax_len=0;

for(inti=1;iN;i++){

for(intj=i-1;j=0;j--){

if(a[i]a[j]){

dp[i]=dp[j]+1;

break;

}

}

printf(%d,dp[i]);

max_len=max(max_len,dp[i]);

}

printf(%d,max_len);

}

第2题问答题

神奇的口袋

有一个神奇的口袋，总的容积是40，用这个口袋可以变出一些物品，这些物品的总体积必须是40。John现在

有n个想要得到的物品，每个物品的体积分别是a1，a2……an。John可以从这些物品中选择一些，如果选出的

物体的总体积是40，那么利用这个神奇的口袋，John就可以得到这些物品。现在的问题是，Joh