#P18359. Insert AB or BA

Insert AB or BA

Insert AB or BA

题目描述

给定两个仅由字符 A 和 B 组成的字符串 SS、TT。

你可以按任意顺序,进行任意次以下两种操作,也可以不进行操作:

  • 在 SS 的任意位置插入字符串 AB,代价为 XX。
  • 在 SS 的任意位置插入字符串 BA,代价为 YY。

插入位置也可以是字符串的最前面或最后面。每次操作都针对当前字符串。

判断能否通过这些操作把 SS 变成 TT。如果可以,求最小总代价。

输入格式

第一行两个字符串 SS、TT,用一个空格隔开。

第二行两个整数 XX、YY,分别表示插入 AB 和插入 BA 的代价。

输出格式

如果可以把 SS 变成 TT,输出最小总代价;否则输出 −1-1。

数据范围

  • SS、TT 仅由字符 A、B 组成。
  • 1≤∣S∣≤∣T∣≤80001\le |S|\le |T|\le 8000。
  • XX、YY 是整数,且 1≤X,Y≤1091\le X,Y\le 10^9。
  • 每个输入文件只有一组数据。

样例输入 1

AB ABAABB
5 3

样例输出 1

8

样例输入 2

AAAAAA AAAAAA
2 3

样例输出 2

0

样例输入 3

AAAAA BBBBBBB
9982 44353

样例输出 3

-1

样例输入 4

AAABBABABBBBBBABBABBA AAABABBABABBABBBBBABBBBBAAAAABBABABBAABBA
1 100000

样例输出 4

300007

样例解释

样例 1 中,从 AB 出发,先在第 1、2 个字符之间插入 BA,得到 ABAB;再在当前字符串第 3、4 个字符之间插入 AB,得到 ABAABB。总代价为 3+5=83+5=8,可以证明这是最小值。