中国建设企业银行网站首页,东莞企业画册设计制作公司报价,抖音代运营培训,网站首页引导页模版题意#xff1a; 给你一个长度为 nnn 的 010101串 #xff0c;你有两种操作#xff1a; 1.将一个子串翻转#xff0c;花费 XXX 2.将一个子串中的0变成1#xff0c;1变成0#xff0c;花费 YYY 求你将这个01串变成全是1的串的最少花费。 首先#xff0c;我们可以将串按照0… 题意 给你一个长度为 nnn 的 010101串 你有两种操作 1.将一个子串翻转花费 XXX 2.将一个子串中的0变成11变成0花费 YYY 求你将这个01串变成全是1的串的最少花费。 首先我们可以将串按照0,10,10,1这划分例如«00011001110»−gt;«000»«11»«00»«111»«0»«00011001110» -gt; «000» «11» «00» «111» «0»«00011001110»−«000»«11»«00»«111»«0»可以看出只有相邻的010101串间进行操作才是有意义的。 将左面的 000 串与右面的 111 进行 “交换” 有两种办法 1.将000 同一修改为 111. 2.将该串与靠右的一个111串交换即翻转). 由于题中X,YX,YX,Y 是一个确定的值这就使得我们每次的交换方法一定是相同的。然而如果一直用第 222 种方法进行变换最终必定还要使用一次 111 操作来将已经连城的一排 000, 统一修改为 111。即最小花费为(p−1)∗min(x,y)y(p-1)*min(x,y)y(p−1)∗min(x,y)yppp 为原序列中 000 串的数量。 Code: #includecstdio
#includealgorithm
#includecstring
#includeiostream
using namespace std;
const int maxn 300000 4;
int nex[maxn];
char str[maxn];
int main()
{int n, x, y, cnt 0;scanf(%d%d%d,n,x,y);scanf(%s,str 1);str[0] str[1] 1 ? 0 : 1; for(int i 1;i n; i) if(str[i] 0 str[i] ! str[i - 1]) cnt;if(cnt 0) printf(0);else cout (long long)(cnt - 1) * min(x, y) y;return 0;
}转载于:https://www.cnblogs.com/guangheli/p/9845121.html
