[ABC346D] Gomamayo Sequence 讲解

· · 题解

题目
一眼 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;
}