电子学会青少年软件编程(C语言四级)等级考试真题试卷(2022年6月)-附.pdfVIP

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

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

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

第1题问答题

公共子序列

我们称序列Z=z1,z2,...,zk是序列X=x1,x2,...,xm的子序列当且仅当存在严格上升的序列i1,

i2,...,ik，使得对j=1,2,...,k,有xij=zj。比如Z=a,b,f,c是X=a,b,c,f,b,c的子序列。现在

给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是

X的子序列也是Y的子序列。

时间限制：3000

内存限制：65536

输入

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串

之间由若干个空格隔开。

输出

对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

样例输入

abcfbcabfcab

programmingcontest

abcdmnp

样例输出

4

2

0

答案#includebits/stdc++.h

#includestring

usingnamespacestd;

intf[1000][1000];

intmain()

{

stringa,b;

while(cinab)

{

intn=a.size();

intm=b.size();

memset(f,0,sizeof(f));

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

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

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

for(inti=1;i=n;i++)

{

for(intk=1;k=m;k++)

{

if(a[i-1]==b[k-1])

{

f[i][k]=max(f[i][k],f[i-1][k-1]+1);

}

else

{

f[i][k]=max(f[i][k-1],f[i-1][k]);

}

}

}

coutf[n][m]endl;

}

return0;

}

第2题问答题

硬币问题

有N（不大于100）种硬币，编号为1至N，已知每种硬币的重量（不超过100的正整数）和面额（不超过100的

正整数），每种硬币数量不限