← 返回题目列表

AtCoder · utpc2024_i

I. 插入 AB 或 BA

中文机器翻译题面 查看原题

配点 : 100 点

問題文

A 和 按字典顺序比较 B 长度为几的字符串 S 和 按字典顺序比较 T 。 对于

下面 2 种操作,0 考虑进行任意次数的操作,可以按任意顺序进行。

  • S 中的任意位置 插入 AB 插入。成本为 X 需要。
  • S 中的任意位置 插入 BA 插入。成本为 Y 需要。

此外,插入也可以在开头或结尾进行。

S 该值应乘以 T 判断是否可以与之匹配,如果可能,请求出所需的总成本的最小值。

制約

  • X, Y 是一个整数
  • S, T 是 您也可以写 A 和 按字典顺序比较 B 长度为几的字符串
  • 1 \le |S| \le |T| \le 8000
  • 1 \le X \le 10^9
  • 1 \le Y \le 10^9

入力

输入是按以下格式从标准输入给出的。

S T
X Y

出力

S 该值应乘以 T 如果可以与之匹配,所需的总成本的最小值为 1 行输出。如果不可能 输出 -1 。


入力例 1

AB ABAABB
5 3

出力例 1

8

一开始, 在第S = AB 通过以下操作可以实现。S 该值应乘以 T= ABAABB 。 替换为

  • S = AB 可以得到第 1 信和 将其重写为 2 在字符之间 BA 。 由S = ABAB 变为。
  • S = ABAB 可以得到第 3 信和 将其重写为 4 在字符之间 AB 。 由S = ABAABB 变为。

在这种情况下,所需成本的总和为 3 + 5 = 8 。实际上,这也是所需总成本的最小值。


入力例 2

AAAAAA AAAAAA
2 3

出力例 2

0

入力例 3

AAAAA BBBBBBB
9982 44353

出力例 3

-1

入力例 4

AAABBABABBBBBBABBABBA AAABABBABABBABBBBBABBBBBAAAAABBABABBAABBA
1 100000

出力例 4

300007