题目描述

难度分:$845$

输入$n(2 \leq n \leq 2 \times 10^5)$，长为$n$的01字符串$s$，长为$n$的数组$a(1 \leq a[i] \leq 10^9)$。

修改$s$，使其中恰好包含一对相邻相同字符。例如10010是符合要求的，11001是不符合要求的（有两对相邻相同字符11和00）。

修改$s[i]$的代价是$a[i]$。输出最小总代价。

输入样例$1$

5
00011
3 9 2 6 4

输出样例$1$

7

输入样例$2$

4
1001
1 2 3 4

输出样例$2$

0

输入样例$3$

11
11111100111
512298012 821282085 543342199 868532399 690830957 973970164 928915367 954764623 923012648 540375785 925723427

输出样例$3$

2286846953

算法

前后缀分解+动态规划

状态定义

$pre[i][k]$表示结尾为$k(k=0,1)$，且前缀$[1,i]$为01交替串的修改代价。$suf[i][k]$表示开头为$k$，且后缀$[i,n]$为01交替串的修改代价。

状态转移

以$pre$数组为例说明，初始情况下$pre[0][0]=pre[0][1]=0$（前缀为空不需要任何代价）。如果期望$s[i]=$0，那前一个位置$i-1$就必须是1，转移来源为$pre[i-1][1]$。当前$s[i]=$0不需要代价，$s[i]=$1需要付出$c[i]$的修改代价。状态转移方程为$pre[i][0]=pre[i-1][1]+cost$，同理如果期望$s[i]=$1，则状态转移方程为$pre[i][1]=pre[i-1][0]+cost$，其中$cost$取决于$s[i]$是不是本来就为期望的字符。

枚举+前后缀分解

最后枚举相邻相等的位置$(i,i+1)$（$i \in [1,n-1]$），如果$s[i]=s[i+1]=$0，那前缀$[1,i-1]$就是以1结尾的01交替串，后缀$[i+2,n]$就是以1开头的01交替串；如果$s[i]=s[i+1]=$1，那前缀$[1,i-1]$就是以0结尾的01交替串，后缀$[i+2,n]$就是以0开头的01交替串。维护$min(pre[i-1][0]+suf[i+2][0]+cost_1,pre[i-1][1]+suf[i+2][1]+cost_0)$的最小值即可，其中$cost_k$是将$s[i]$和$s[i+1]$都变为$k(k=0,1)$的代价。

复杂度分析

时间复杂度

动态规划的预处理时间复杂度为$O(n)$（状态数量$O(n)$，单次转移$O(1)$）；枚举两个相邻的相等位置时间复杂度为$O(n)$，更新答案时间复杂度为$O(1)$。因此，整个算法的时间复杂度还是$O(n)$。

空间复杂度

除了输入的$s$串和$c$数组，空间瓶颈就在于两个DP数组$pre$和$suf$，都是$O(n)$的，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int n, c[N];
char s[N];
LL pre[N][2], suf[N][2];

int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    suf[n + 1][0] = suf[n + 1][1] = 0;
    for(int i = 1, j = n; i <= n; i++, j--) {
        pre[i][0] = pre[i - 1][1] + (s[i] != '0'? c[i]: 0);
        pre[i][1] = pre[i - 1][0] + (s[i] != '1'? c[i]: 0);
        suf[j][0] = suf[j + 1][1] + (s[j] != '0'? c[j]: 0);
        suf[j][1] = suf[j + 1][0] + (s[j] != '1'? c[j]: 0);
    }
    LL ans = 1e18;
    for(int i = 1; i < n; i++) {
        ans = min(ans, pre[i - 1][0] + suf[i + 2][0] + (s[i] == '1'? 0: c[i]) + (s[i + 1] == '1'? 0: c[i + 1]));
        ans = min(ans, pre[i - 1][1] + suf[i + 2][1] + (s[i] == '0'? 0: c[i]) + (s[i + 1] == '0'? 0: c[i + 1]));
    }
    printf("%lld\n", ans);
    return 0;
}