玄神的字符串

NC232578. 玄神的字符串

描述

玄神有一条珍藏多年的神奇字符串。因为某种原因，该字符串只由数字0和数字1组成。但是最近，他开始对字符串感到厌烦，所以他想将这个字符串删除。他可以任意进行以下三种操作，每种操作的次数不限：
1）选择字符串中的一个0和一个1，将他们删除，代价为a；
2）选择字符串中两个位置不同的0或者两个位置不同的1，将他们删除，代价为b；
3）将字符串中的一个0变成1或将字符串中的一个1变成0，代价为c。
聪明的你能不能帮帮玄神，求出将这条神奇字符串删除成空字符串（不含任何字符的字符串）的最小代价为多少？

输入描述

第一行包括一个仅由数字0和数字1构成的字符串s，s的长度不超过 $50000$ ,保证s的长度为偶数
第二行包括三个整数a、b、c，分别代表上述三种操作的代价。保证 $1\leq a,b,c\leq 10000$

输出描述

输出包括一个整数，表示删除该字符串的最小代价

示例1

输入:

0110011001
3 4 5

输出:

示例2

输入:

0110011001
10 2 3

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 532K, 提交时间: 2022-01-17 17:13:06

#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;cin>>s;
	int on=0,ze=0,n=s.size();
	for(int i=0;i<n;i++) if(s[i]=='0') ze++;else on++;
	int a,b,c;cin>>a>>b>>c;
	a=min(a,b+c);
	b=min(b,a+c);
	int ans=min(on,ze)/2*2*min(a,b)+min(on,ze)%2*a+abs(on-ze)/2*b;
	cout<<ans<<endl;
}

Python3 解法, 执行用时: 40ms, 内存消耗: 5040K, 提交时间: 2022-01-16 16:00:06

s = list(input())
a,b,c = map(int,input().split())
d = s.count('0')
f = s.count('1')
if a < b:
    sumn = min(d,f)*a
    last = max(d,f) - min(d,f)
    sumn += min(b,a+c)*last//2
else:
    sumn = (d//2+f//2)*b
    if d%2 == 1:
        sumn += min(b+c,a)
print(sumn)