题目链接

https://codeforces.com/contest/1443/problem/B

解题思路

也算是dp吧。
转移（抽象讲解）：
对于每个连通块（特指为1），无非是选择单独引爆，或者选择与前面的连通块相连通。
dp[i]表示引爆前i个连通块的最小花费，那对于第i个连通块而言，选择单独引爆时dp[i]=dp[i-1]+a；选择与前面的连通块连通引爆时，由于dp[i-1]表示的就是前i-1个引爆的最小花费，所以其实对于第i个连通块来说，只需要与前面的连通块相连，不需要再加上引爆的费用了，而连通的费用就是第i个连通块前面相邻的0的个数*b。

AC代码

#include<bits/stdc++.h>
#define int long long
const int N=1e5+100;
const int inf=0x3f3f3f3f;
using namespace std;
int T,a,b,n,cnt,cnt0,cnt1;
string str;
vector<int> cnttt0,cnttt1;//cnttt0[i]表示第i个0连通块的0的个数；cnttt1[i]表示第i个1连通块的1的个数。
int dp[N];
signed main()
{
    cin>>T;
    while(T--)
    {
        cin>>a>>b;
        cin>>str;
        n=str.size();
        str=' '+str;
        cnttt0.clear();
        cnttt1.clear();
        for(int i=1;i<=n;i++)
        {
            cnt1=0,cnt0=0;

            if(i==1 && str[i]=='0')
            while(i<=n && str[i]=='0') i++;//清除前导0

            while(i<=n && str[i]=='1') cnt1++,i++;    
            if(cnt1) cnttt1.push_back(cnt1);//统计1连通块

            while(i<=n && str[i]=='0') cnt0++,i++;
            if(cnt0) cnttt0.push_back(cnt0);//统计0连通块

            i--;
        }

        dp[0]=a;//初始化，如果就一个1连通块时
        for(int i=1;i<cnttt1.size();i++)
        dp[i]=min(cnttt0[i-1]*b+dp[i-1],dp[i-1]+a);

        cout<<dp[cnttt1.size()-1]<<endl;    
    }
}