题目链接

https://codeforces.com/problemset/problem/998/C

解题思路

别人的正确思路：

任何一段0 1序列都可以看做是一串 0 然后用 1 切割开。首先，因为我们是要把目标串变成全1串，所以开头的1（和结尾的1）我们可以不去管它，所以我们可以把所有的串看做是这种（开头的1和结尾的1无所谓就全都省略）然后我们可以怎么做呢？例如：000 1 000 1 0000 1 00 1 00这个串，因为上面操作的花费与段的长度无关，所以我们可以把相邻的1合成一个1，相邻的0合成一个0。所以原串就可以转化成 0 1 0 1 0 1 0 1 0。
假设0分成的段的数量是num。

第一种方法，将最左边的01翻转，得到1 00 1 0 1 0 1 0；再把左侧的00 1翻转，得到11 000 1 0 1 0；以此类推，得到111 0000 1 0，得到1111 00000。翻转的次数为num-1，再对连续的0进行变换这种方法的花费为 （num-1）* x+y。

第二种方法，我们直接对每一段0实施操作二，使得其变为全1串，这样的花费是num * y。

所以显然，当x<=y时，我们选择第一种方案，当x>y时，我们选择第二中方案，统计0的段数，直接输出结果即可。

我的正确思路：
其实我自己都不知道我的思路，因为原来见过一道题，和这个很像，那道题myq是用dp做的，所以我一直在想如何dp，结果稀里糊涂的dp出来了（如果你要问myq是谁，他是wf第一，但这不算什么，更重要的是，他是我儿子）
dp[i][0/1]的含义为前i个单元全部变成1的最小花费，第二维为0表示第i个单元没有与第i-1个单元发生翻转操作，为1表示第i个单元与第i-1个单元发生了翻转操作。（单元的含义为连续相同的1序列或0序列）
我不行了，我想试着讲解一下，结果发现我并不能讲出来……就是蒙了个AC……

别人的AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,x,y,cnt;
string str;
int main()
{
    cin>>n>>x>>y;
    cin>>str;

    if(str[0]=='0') cnt++;
    for(int i=1;i<n;i++)
    if(str[i]=='0' && str[i-1]!='0') cnt++;

    if(cnt==0)//特判
    {
        cout<<0<<endl;
        return 0;
    }
    if(x<=y) cout<<(cnt-1)*x+y<<endl;
    else cout<<cnt*y<<endl;
    return 0;
}

我的AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
int cnt,n,x,y,f;
ll dp[N][2];
string str;
int main()
{
    cin>>n>>x>>y;
    cin>>str;
    f=str[0]-'0';
    cnt=1;
    for(int i=1;i<n;i++)
    {
        while(str[i]==str[i-1] && i<n) i++;
        if(i==n) break;
        cnt++;
    }
//    cout<<cnt<<endl;
    if(cnt==1)
    {
        cout<<(f==1?0:y)<<endl;
        return 0;
    } 
    memset(dp,0x3f,sizeof dp);
    if(f) dp[1][0]=y,dp[1][1]=y;
    else dp[1][0]=y,dp[1][1]=x+y;
    f^=1;
    for(int i=2;i<=cnt;i++,f^=1)
    {
        if(f) dp[i][1]=min(dp[i-1][1],dp[i-1][0])+x,dp[i][0]=min(dp[i-1][0],dp[i-1][1]);
        else  dp[i][1]=min(dp[i-1][1],dp[i-1][0])+x,dp[i][0]=min(dp[i-1][1],dp[i-1][0]+y);
    }
//    for(int i=2;i<=cnt;i++)
//    cout<<min(dp[i][0],dp[i][1])<<endl;
    cout<<min(dp[cnt][0],dp[cnt][1])<<endl;
    return 0;
}