307764: CF1411D. Grime Zoo
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Grime Zoo
题意翻译
给定由字符 `0 1 ?` 所组成的字符串 $s$ 和参数 $x,y$,你需要在所有字符为 `?` 的位置填入字符 `0` 或者 `1`。 我们规定这个字符串的价值为: `01` 子序列的数量 $\times x\ +$ `10` 子序列的数量 $\times y$ 求字符串价值最小值。 $1\leq |s|\leq10^5,0\leq x,y\leq10^6.$题目描述
Currently, XXOC's rap is a string consisting of zeroes, ones, and question marks. Unfortunately, haters gonna hate. They will write $ x $ angry comments for every occurrence of subsequence 01 and $ y $ angry comments for every occurrence of subsequence 10. You should replace all the question marks with 0 or 1 in such a way that the number of angry comments would be as small as possible. String $ b $ is a subsequence of string $ a $ , if it can be obtained by removing some characters from $ a $ . Two occurrences of a subsequence are considered distinct if sets of positions of remaining characters are distinct.输入输出格式
输入格式
The first line contains string $ s $ — XXOC's rap ( $ 1 \le |s| \leq 10^5 $ ). The second line contains two integers $ x $ and $ y $ — the number of angry comments XXOC will recieve for every occurrence of 01 and 10 accordingly ( $ 0 \leq x, y \leq 10^6 $ ).
输出格式
Output a single integer — the minimum number of angry comments.
输入输出样例
输入样例 #1
0?1
2 3
输出样例 #1
4
输入样例 #2
?????
13 37
输出样例 #2
0
输入样例 #3
?10?
239 7
输出样例 #3
28
输入样例 #4
01101001
5 7
输出样例 #4
96