#P17855. [Ontak2019]POD
[Ontak2019]POD
— 末日旅程
给定两个整数序列 和 。求一个最长的公共子序列,使其中任意两个相邻元素的二进制表示至多有 位不同。
也就是说,若所选公共子序列为 ,则对每个 ,必须有
$$\operatorname{popcount}(x_i\mathbin{\mathrm{xor}}x_{i+1})\le k.$$子序列保持原序列中的先后顺序,但不要求连续。长度为0或1的序列自动满足相邻元素限制。
输入格式
第一行三个整数 。
第二行 个整数,描述序列 。第三行 个整数,描述序列 。
输出格式
输出一个整数,表示满足条件的最长公共子序列长度。
数据范围
,,。注意上界 本身也允许出现。
内存限制仅为 32 MB。
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | 5 | |
| 2 | , | 15 |
| 3 | ||
| 4 | ||
| 5 | 40 | |
| 6 | 10 |
原题总约束为20000,而子任务表最大只写到10000;这里保留两者,标程按总约束实现。
样例 1
输入:
3 5 1
1 2 1
2 1 0 1073741824 1
输出:
2