You’ve got a string a1,a2,…,an, consisting of zeros and ones.
Let’s call a sequence of consecutive elements ai,ai + 1,…, aj (1≤ i≤ j≤ n) a substring of string a.
You can apply the following operations any number of times:
Choose some substring of string a (for example, you can choose entire string) and reverse it, paying x coins for it (for example, «0101101» → «0111001»);
Choose some substring of string a (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 y coins for it (for example, «0101101» → «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?

。。。懒得弄格式了凑合看吧我好随便

分析

　　求最小花费让整个字符串变成1，看到最小花费，是不是想到了Dp，想到Dp就条坑里去了，用Dp的话，你会发现状态没法转移，因为它既涉及到了区间反转，又涉及到了区间更新。

　　两种操作还要分类讨论，很麻烦，这两种操作有什么内在联系呢？手动模拟一下会发现，反转一段区间，可以将两段0合并成一段，而区间更新没有限制，除了是一段连续区间外，所以，反转区间和合并区间的操作是等价的，故如果有k段0需要处理，可以先将它们合并成1段，再集中处理，最后一次更新区间肯定是要用的，因为0不可能平白无故变成1，所以讨论一下k-1次处理的选择方式就好，显然是取最小值，因为答案让求最小嘛。

 #include<iostream>

 const int N=3e5+;

 char a[N];

 using namespace std;

 int main(){

     int n,x,y;

     cin>>n>>x>>y>>a+;

     long long cnt=0ll;

     a[]='';

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

         if(a[i]==''&&a[i-]=='')

             cnt++;

     if(cnt==)cout<<;

     else cout<<(cnt-)*min(x,y)+y;

 }

巴特西

CF 997A

分析

最新文章

热门文章