题目名称 3765. 01串
输入输出 zerone.in/out
难度等级 ★★
时间限制 3000 ms (3 s)
内存限制 512 MiB
测试数据 10
题目来源 Gravatarlihaoze 于2022-09-25加入
开放分组 全部用户
提交状态
分类标签
动态规划
分享题解
通过:2, 提交:3, 通过率:66.67%
Gravatarlihaoze 100 0.000 s 0.00 MiB C++
Gravatarlihaoze 100 3.058 s 232.69 MiB C++
Gravatarlihaoze 40 0.000 s 0.00 MiB C++
本题关联比赛
EYOI与SBOI开学欢乐赛10th
关于 01串 的近10条评论(全部评论)

3765. 01串

★★   输入文件:zerone.in   输出文件:zerone.out   简单对比
时间限制:3 s   内存限制:512 MiB

【题目描述】

给定两个 01串 $a$, $b$,每次操作选择 $a$ 上两个位置上的值,然后反转这两个值(即异或1),若两位置相邻,则一次操作的代价为 $x$,否则为 $y$。 你的任务是通过最少的代价,使得 $a = b$,或者判断没有方法使得两串相等。

【输入格式】

第一行,包括三个正整数 $n$, $x$, $y$。 接下来两行,分别包括一个字符串 $a$, $b$,长度均为 $n$。

【输出格式】

输出一行一个答案,如果若干次操作后可以使得两串相等,输出一个最小的代价,否则输出 $-1$。

【样例输入1】

6 2 11
000001
100000

【样例输出1】

10

【样例输入2】

5 8 9
01001
00101

【样例输出2】

8

【数据规模与约定】

对于 20% 的数据,$n \le 3000, y \le x$。 

另外 80% 的数据,$n \le 5000$。 

对于 100% 的数据,$5 \le n \le 5000, 1 \le x, y \le 10^9$。