#1469. 「NnOI R2-T4」Colorful Days♪

「NnOI R2-T4」Colorful Days♪

题目描述

给出如下定义:

  1. 定义 AB AB 为 A A 数组后拼接 B B 数组。
  2. 定义 A0={} A^{0}=\{\} (即空数组),且对 i=1,2,3,⋯i=1,2,3,\cdots,Ai=Ai−1A A^{i}=A^{i-1}A。
  3. 定义 LCS⁡(A,B) \operatorname{LCS}(A,B) 为 A A 数组和 B B 数组的最长公共子序列长度。

现给定长度为 n n 的数组 S S 和长度为 m m 的数组 T T ,数组中的数均为正整数。

你现在需要找到最小的非负整数 kk,使得 LCS⁡(Sk,T) \operatorname{LCS}(S^k,T) 最大。

出题人很仁慈,如果你无法最小化 kk,你也可以拿到一部分分数。

输入格式

第一行四个整数 n,m,c1,c2 n,m,c_1,c_2 ,后两个整数为输出参数 0 或 1。

第二行 n n 个正整数,代表 S S 数组。

第三行 m m 个正整数,代表 T T 数组。

输出格式

输出两个整数 c1⋅LCS⁡(Sk,T) c_1 \cdot \operatorname{LCS}(S^k,T) 和 c2⋅kc_2\cdot k。

样例

3 4 1 1
23 34 53
53 25 23 34
3 2
9 10 1 1
15 12 26 21 26 21 23 12 23
26 11 21 15 16 15 12 23 17 12
7 3

题目来源:洛谷 P9572