Codeforces Round #493 (Div. 2) C. Convert to Ones 乱搞_构造

每次肯定是对一段连续的 $0$ 或者 $1$ 进行操作.

对于一段连续的 $0$，要么直接变为 $1$，要么与右面的连续的 $1$ 交换.

如果与右面的 $1$ 翻转更加合适，那么就肯定会一直翻转，并在不能交换的时候变为 0.

否则，就会一直将子序列变为 $0$.

即 $ans=min(num[0]\times y,(num[0]-1)\times x+y)$

#include <cstdio>

#include <algorithm>

#define ll long long

#define setIO(s) freopen(s".in", "r" , stdin)

using namespace std;

ll x, y;

char str[300005];

int n ,a[2], i, pre = -1;

int main()

{

    // setIO("input");

    scanf("%d%lld%lld%s", &n, &x, &y, str + 1);

    for(i = 1; i <= n ; ++ i)

    {

        int cur = str[i] - '0';

        scanf("%d", &cur);

        if(cur != pre)  ++ a[cur], pre = cur;

    }

    printf("%lld\n", max(1ll*0, min(1ll * a[0] * y, 1ll * (a[0] - 1) * x + y)));

    return 0;

}

巴特西

Codeforces Round #493 (Div. 2) C. Convert to Ones 乱搞_构造_好题

最新文章

热门文章