本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-28 21:13:16

题目
一眼 dp。

做法一：

从一端开始 dp，设 $f_{i,0/1,0/1}$ 为进行到第 $i$ 位，最后一位为 $0/1$，且是或不是（$0/1$）好字符串。
易得转移方程：
$$f_{i,0,0}=f_{i-1,1,0}+[s_i=1]\times c_i$$ $$f_{i,1,0}=f_{i-1,0,0}+[s_i=0]\times c_i$$ $$f_{i,0,1}=\min(f_{i-1,1,1},f_{i-1,0,0})+[s_i=1]\times c_i$$ $$f_{i,1,1}=\min(f_{i-1,0,1},f_{i-1,1,0})+[s_i=0]\times c_i$$ 初始化：
$$f_{2,0,0}=[s_1=0]\times c_1+[s_2=1]\times c_2$$ $$f_{2,1,0}=[s_1=1]\times c_1+[s_2=0]\times c_2$$ $$f_{2,0,1}=[s_1=1]\times c_1+[s_2=1]\times c_2$$ $$f_{2,1,1}=[s_1=0]\times c_1+[s_2=0]\times c_2$$ 直接放代码：

#include<bits\/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define repe(i,x,y,z) for(int i=x;i<=y;i+=z)
#define eper(i,x,y,z) for(int i=x;i>=y;i-=z)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inl inline
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,c[N],f[N][5][5];
string s;
signed main(){
	fst;
	memset(f,0x3f,sizeof(f));
	cin>>n>>s;
	s='2'+s;
	rep(i,1,n) cin>>c[i];
	f[2][0][0]=(s[1]=='0')*c[1]+(s[2]=='1')*c[2];
	f[2][1][0]=(s[1]=='1')*c[1]+(s[2]=='0')*c[2];
	f[2][0][1]=(s[1]=='1')*c[1]+(s[2]=='1')*c[2];
	f[2][1][1]=(s[1]=='0')*c[1]+(s[2]=='0')*c[2];
	rep(i,3,n){
		f[i][0][0]=f[i-1][1][0]+(s[i]=='1')*c[i];
		f[i][1][0]=f[i-1][0][0]+(s[i]=='0')*c[i];
		f[i][0][1]=min(f[i-1][1][1],f[i-1][0][0])+(s[i]=='1')*c[i];
		f[i][1][1]=min(f[i-1][0][1],f[i-1][1][0])+(s[i]=='0')*c[i];
	}
\/\/	rep(i,1,n) cout<<f[i][0][0]<<' '<<f[i][0][1]<<' '<<f[i][1][0]<<' '<<f[i][1][1]<<endl;
	cout<<min(f[n][0][1],f[n][1][1]);
	return 0;
}

做法二：

考虑好字符串的本质，实际就是中间两位相同的两个交错字符串，所以我们可以从两端进行 dp，设 $f_{i,0/1}$ 为以第 $i$ 为结尾，且结尾是 $0/1$ 的前缀 dp；设 $g_{i,0/1}$ 为以第 $i$ 位开头，且开头为 $0/1$ 的后缀 dp。
转移方程与做法一类似，直接放代码：

#include<bits\/stdc++.h>
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define repe(i,x,y,z) for(int i=x;i<=y;i+=z)
#define eper(i,x,y,z) for(int i=x;i>=y;i-=z)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define inl inline
#define INF LLONG_MAX
using namespace std;
const int N=2e5+5;
int n,c[N],f[N][5],g[N][5],ans=INF;
string s;
signed main(){
	fst;
	cin>>n>>s;
	s=' '+s;
	rep(i,1,n) cin>>c[i];
	rep(i,1,n){
		f[i][0]=(s[i]=='1')*c[i]+f[i-1][1];
		f[i][1]=(s[i]=='0')*c[i]+f[i-1][0];
	}
	per(i,n,1){
		g[i][0]=(s[i]=='1')*c[i]+g[i+1][1];
		g[i][1]=(s[i]=='0')*c[i]+g[i+1][0];
	}
	rep(i,1,n-1){
		ans=min(ans,f[i][0]+g[i+1][0]);
		ans=min(ans,f[i][1]+g[i+1][1]);
	}
	cout<<ans;
	return 0;
}