C. Convert to Ones
题目大意:一个长度为n的01字符串,反转任何一个连续区间价值为x,将任意一个全为0的子区间改为1价值为y,求将字符串全变为1的最小价值。
这题也是看了好久才找到规律。
我们可以发现,若要用x操作,就是要把1通过反转连起来,那么剩下的0的子区间就用y操作。
那么要用多少次x操作呢,看似很难确定。。
设0的子区间个数为m,我们不难发现,将所有1连在一起需要m-1次x操作。
那么如果我们不执行m-1次x操作,设执行x操作a次(a<m-1),那么代价为a * x+(m-a) * y;
若x<y,那么则是a越大越好,那么a取m-1;
若x>y,就直接执行m次y操作价值会最小.
所以答案就是min((m-1) * x+y,m * y);
注意m==0时要特判。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%lld",a)
using namespace std;
int n,x,y;
ll cnt,ans;
char str[1][300050];
int read()
{
int s=0,t=1; char c;
while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
return s*t;
}
int main()
{
n=read(); x=read(); y=read();
scanf("%s",str[0]);
for (int i=0;i<n;i++)
if (str[0][i]=='1'&&str[0][i-1]=='0') cnt++;
if (str[0][n-1]=='0') cnt++;
if (cnt==0) ans=0;
else ans=min((cnt-1)*x+y,cnt*y);
out(ans);
return 0;
}
