题目详情题解（0）讨论（0）提交记录（0）

AT_utpc2024_i.Insert AB or BA

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定由 A 和 B 组成的字符串 SS 和 TT。

可以按照喜欢的顺序、任意次数（0 次或以上）进行以下两种操作：

  • 在 SS 的任意位置插入 AB。每次操作的花费为 XX。
  • 在 SS 的任意位置插入 BA。每次操作的花费为 YY。

此外，可以在 SS 的开头或结尾插入。

请判断能否通过上述操作将 SS 变为 TT，如果可以，求出所需总花费的最小值。

输入格式

输入通过标准输入按以下格式给出。

SS TT XX YY

输出格式

如果可以将 SS 变为 TT，请输出所需总花费的最小值。否则，输出 -1。

输入输出样例

  • 输入#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

一开始，$S = $ AB。可以通过如下操作将 SS 变为 $T= $ ABAABB。

  • 在 $S = $ AB 的第 1 个字符和第 2 个字符之间插入 BA。此时 $S = $ ABAB。
  • 在 $S = $ ABAB 的第 3 个字符和第 4 个字符之间插入 AB。此时 $S = $ ABAABB。

在这种情况下，总花费为 3+5=83 + 5 = 8。事实上，这已经是所需的最小总花费。

数据范围

  • XX、YY 为整数。
  • SS、TT 均为仅由 A 和 B 组成的字符串。
  • 1≤∣S∣≤∣T∣≤80001 \le |S| \le |T| \le 8000
  • 1≤X≤1091 \le X \le 10^9
  • 1≤Y≤1091 \le Y \le 10^9

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页