Skip to content

14145: 【原4145】拯救锡安

题目

题目描述

author: Yifan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4145

Description

崔妮蒂手上有一串由0和1组成的长度为n的字符串. 她能对该字符串进行任意多次下面两种操作.

  1. 选择任一子串进行翻转, 例如0101101->0111001. 进行一次此操作会花费x点能量.

  2. 选择任一子串将每个字符取反(把0换成1, 把1换成0), 例如0101101->0110001. 进行一次此操作会花费y点能量.

为了拯救锡安, 崔妮蒂需要把该字符串变成全为1的串. 请问最少需要多少能量点数才能达到这一目的?

Input Format

第一行是三个正整数n, x, y. (1 <= n <= 300000, 0 <= x, y <= 10^9).

第二行是一个长度为n的01字符串.

Output Format

将01字符串变成全为1的串所需的最少能量点数.

Sample1 Input

5 1 10
01000

Sample1 Output

11

Sample2 Input

5 10 1
01000

Sample2 Output

2

Sample3 Input

7 2 3
1111111

Sample3 Output

0

Note

第一个样例：01000->10000->11111, 花费的能量点数为1+10=11.

第二个样例：01000->11000->11111, 花费的能量点数为1+1=2.

第三个样例：字符串已经是全为1的串了, 不需要花费能量.

WashSwang's solution 

#include <iostream>
using namespace std;
char t,cur,last;
int n,frag;
long long x,y;
int main() {
    scanf("%d%lld%lld",&n,&x,&y);
    getchar();
    last='1';
    for (int i=0;i<n;++i){
        cur=getchar();
        if (cur=='0'&&last=='1') frag++;
        last=cur;
    }
    if (frag==0) printf("%d",0);
    else
    printf("%lld",min((frag-1)*x+y,frag*y));
    return 0;
}