D. 最长公共子序列¶

分数：100分

In nature we never see anything isolated, but everything in connection with something else which is before it, beside it, under it and over it.

背景¶

【提醒：附件 Tab 中有 baseline 和数据生成器】

最长公共子序列（Longest Common Subsequence, LCS）是一种常见的字符串匹配算法。它的应用场景非常广泛，例如 DNA 序列比对、版本控制、代码相似度检测等。LCS 问题是一个经典的动态规划问题，可以用动态规划、回溯、贪心等多种方法解决。

说明¶

给定两个序列，长度分别是 len1 和len2 ，输出他们最长公共子序列的长度。

输入输出¶

输入文件 input.dat 包含两个序列，格式如下：

首先是两个 size_t 类型的整数 len1 和 len2，分别表示两个序列的长度。

接下来是两个长度分别为 len1 和 len2 的 element_t 类型的数组，分别表示两个序列。本题中 element_t 是一个 int 类型。

输出文件 output.dat 包含一个 size_t 类型的整数，表示最长公共子序列的长度。

样例¶

input.dat

5 6
1 2 3 4 5
1 2 3 4 5 6

output.dat

5

评测环境¶

容器镜像：hpckit，使用 clang++ 编译器编译。程序会在配备 Kunpeng 920 处理器的服务器上运行，可以使用 16 个物理核心。保证这 16 个物理核心在同一个 NUMA 节点上。

内存大小限制为：20GB。

评分方法¶

提交一个 lcs.cpp 文件，包括 lcs 函数，函数签名是：

size_t lcs(element_t* arr_1, element_t* arr_2, size_t len_1, size_t len_2);

编译和执行命令是：

make
OMP_NUM_THREADS=16 ./lcs

评分标准¶

所有结果必须正确，否则不得分。

测试点¶

共 5 个测试点，每个测试点得到正确结果获得基本分数，性能分数与运行时间倒数成正比。

final_score = correct ? base_score + perf_score * min(goal / time, 1) : 0

附件¶

• lcs-handout.tar.gz
• lcs.yaml