洛谷 CF997A Convert to Ones
洛谷 CF997A Convert to Ones
题意翻译
给你一个长度为 nn 的01串( n \leq 310^5n*≤3∗105 ),你有两种操作:
1.将一个子串翻转,花费 XX
2.将一个子串中的0变成1,1变成0,花费 YY
求你将这个01串变成全是1的串的最少花费。
感谢@litble 提供翻译
题目描述
You've got a string a_1, a_2, \dots, a_na1,a2,…,a**n , consisting of zeros and ones.
Let's call a sequence of consecutive elements a_i, a_{i + 1}, \ldots, a_j ( 1\leq i\leq j\leq n ) a substring of string aa .
You can apply the following operations any number of times:
- Choose some substring of string aa (for example, you can choose entire string) and reverse it, paying xx coins for it (for example, «0101101» \to→ «0111001»);
- Choose some substring of string aa (for example, you can choose entire string or just one symbol) and replace each symbol to the opposite one (zeros are replaced by ones, and ones — by zeros), paying yy coins for it (for example, «0101101» \to→ «0110001»).
You can apply these operations in any order. It is allowed to apply the operations multiple times to the same substring.
What is the minimum number of coins you need to spend to get a string consisting only of ones?
输入格式
The first line of input contains integers nn , xx and yy ( 1 \leq n \leq 300,000, 0 \leq x, y \leq 10^9 ) — length of the string, cost of the first operation (substring reverse) and cost of the second operation (inverting all elements of substring).
The second line contains the string aa of length nn , consisting of zeros and ones.
输出格式
Print a single integer — the minimum total cost of operations you need to spend to get a string consisting only of ones. Print 00 , if you do not need to perform any operations.
输入输出样例
输入 #1复制
输出 #1复制
输入 #2复制
输出 #2复制
输入 #3复制
输出 #3复制
说明/提示
In the first sample, at first you need to reverse substring [1 \dots 2][1…2] , and then you need to invert substring [2 \dots 5][2…5] .
Then the string was changed as follows:
«01000» \to→ «10000» \to→ «11111».
The total cost of operations is 1 + 10 = 111+10=11 .
In the second sample, at first you need to invert substring [1 \dots 1][1…1] , and then you need to invert substring [3 \dots 5][3…5] .
Then the string was changed as follows:
«01000» \to→ «11000» \to→ «11111».
The overall cost is 1 + 1 = 21+1=2 .
In the third example, string already consists only of ones, so the answer is 00
题解:
我们要把01串变成1串,本质上是做什么?
最朴实的做法,是把所有0全部取反。
但是我们要求最小代价,所以这么裸着做肯定是不行。
所以我们开始认真看一下这个“翻转”操作。
什么时候我们用反转是比较优惠的呢?
就是,因为每次变化是不限量的,所以我们出于贪心考虑,一定是把这个串的0都归拢到一起,这样就可以用一次取反操作直接变成1串。
所以我们取反,其实就是归拢0的一个过程。
但是我们还会考虑这么一个问题:就是当我们的x比y大的话,取反就特别浪费。我们还莫不如直接把他们直接一段段取反,这样还会比反转后取反节约一点。
所以我们统计1之间夹0的段数,用long long 输出即可。
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define maxn 300001
using namespace std;
int cnt,n,x,y;
char str[maxn];
int main()
{
scanf("%d%d%d",&n,&x,&y);
scanf("%s",str+1);
str[0]='1';
for(int i=1;i<=n;i++)
if(str[i]=='0' && str[i-1]=='1')
cnt++;
if(cnt==0)
puts("0");
else
printf("%lld\n",(ll)(cnt-1)*min(x,y)+y);
return 0;
}
相关文章
- error: converting to execution character set: Invalid or incomplete multibyte or wide character
- [CSS] Use grid-template to make your CSS Grid declarations more readable
- [Git] How to revert one file changes from one commit
- [React Router] Create a ProtectedRoute Component in React Router (setState callback to force update)
- [Poi] Use Poi to Build an Index.js with Modern JavaScript Features
- [Recompose] Pass a React Prop to a Stream in RxJS
- [Javascript] lodash: memoize() to improve the profermence
- Using HttpClient properly to avoid CLOSE_WAIT TCP connections
- [AngularJS] Store the entry url and redirect to entry url after Logged in
- [Angular] Upgrade existing Angular app to Progressive Web App
- [AngularFire 2] Object Observables - How to Read Objects from a Firebase Database?
- use regular expression instead of ABAP function module to parse attachment
- 【Codeforces 231C】To Add or Not to Add
- 已解决Resource stopwords not found. Please use the NLTK Downloader to obtain the resource:
- PAT 1033. To Fill or Not to Fill (贪心)