abc346D 生成仅一处相同01串的最小代价

给定由0和1组成的字符串s[n]，翻转第i个字符需要花费c[i]，现在修改s，使得有且只有一个i满足s[i]==s[i+1]，求最小花费。
2<=n<=2e5; 1<=c[i]<=1e9

可以动态规划，记dp[i][j][k]表示前i个字符，以j结尾，存在k处相等的最小花费，对每个位置，枚举改与不改两种情况进行转移。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)

const int N = 200005;
const int inf = 1e16;
int n, c[N], dp[N][2][2];
string s;
void solve() {
    cin >> n >> s;
    rep(i,1,n) cin >> c[i];
    if (s[0] == '0') {
        dp[1][0][0] = 0;
        dp[1][0][1] = inf;
        dp[1][1][0] = c[1];
        dp[1][1][1] = inf;
    } else {
        dp[1][0][0] = c[1];
        dp[1][0][1] = inf;
        dp[1][1][0] = 0;
        dp[1][1][1] = inf;
    }
    rep(i,2,n) {
        if (s[i-1] == '0') {
            dp[i][0][0] = dp[i-1][1][0];
            dp[i][0][1] = min(dp[i-1][0][0],dp[i-1][1][1]);
            dp[i][1][0] = c[i] + dp[i-1][0][0];
            dp[i][1][1] = c[i] + min(dp[i-1][1][0],dp[i-1][0][1]);
        } else {
            dp[i][0][0] = c[i] + dp[i-1][1][0];
            dp[i][0][1] = c[i] + min(dp[i-1][0][0],dp[i-1][1][1]);
            dp[i][1][0] = dp[i-1][0][0];
            dp[i][1][1] = min(dp[i-1][0][1],dp[i-1][1][0]);
        }
    }
    cout << min(dp[n][0][1],dp[n][1][1]) << "\n";
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}