题目链接：https://atcoder.jp/contests/agc066/tasks/agc066_d

题目大意：给你一个 $AB$ 串，保证 $A\le \frac{n + 1}{2}$ ，每次可以交换 $i$ 和 $i + 1$ 的字符，代价为 $w_{i + 1}$ ，要求最小的代价满足：任意两个 $A$ 不相邻。

我的做法

观察到一个事情：考任意一种可能成为最优方案的方案，一定可以表示成某几个位置的展开。

展开的意思是是说：选择一个 $A$ ，然后从左到右依次将 $A$ 推开，直到某个小区间内没有 $A$ 相邻。

举个例子：$BBBAAABBB$ ，选择中间的 $A$ ，那么中间的 $A$ 就会想着把周围的 $A$ 推开，推成：$BBABABABB$ 。

证明的话，考虑每个 $A$ 是往左移还是往右移的，显然，每一段往左移和每一段往右移中间存在一个数字是不动，否则一定可以更加优秀，所以，每一个不动和左边的往左移动，和右边的往右移动构成了上面所描述的一个小区间。

那么处理出所有的这些区间就行了，处理方法就是把 $A$ 看成 $1$ ，把 $B$ 看成 $-1$ ，然后在折线法左右第一次出现等高的位置，就是区间的左右端点。

然后转移就行了，时间复杂度 ： $O(n)$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
void get_char_array(char *s){
    static char st[N];
    cin >> st;
    memcpy(s + 1, st, sizeof(char) * strlen(st));
}
int n;
struct node{
    int y, next;
    LL c;
}a[N]; int len, las[N];
void ins(int x, int y, LL c){a[++len] = {y, las[x], c}; las[x] = len;}
char st[N];
int pre[N * 2], val[N];
int ll[N], rr[N];
LL cost[N], f1[N], f2[N];
LL dp[N];
int main(){
    int T;
    cin >> T;
    while(T--){
        cin >> n;
        get_char_array(st + 1);

        n += 2;
        st[1] = st[n] = 'B';

        for(int i = 1; i <= n; i++){
            if(st[i] == 'A') val[i] = 1;
            else val[i] = -1;
        }

        LL ans = 0ll;
        for(int i = 3; i < n; i++){
            cin >> cost[i];
            cost[i] += cost[i - 1];
            f1[i] = f1[i - 2] + cost[i];
            f2[i] = f2[i - 1];
            if(val[i] == 1) f2[i] = f2[i] + cost[i];
        }
        

        int sum = n;
        fill(pre + 1, pre + n + n + 1, -10ll);
        pre[n] = 0ll;
        for(int i = 1; i <= n; i++){
            sum += val[i];
            ll[i] = pre[sum] + 1;
            pre[sum] = i;
        }
        sum = n;
        fill(pre + 1, pre + n + n + 1, -10ll);
        pre[n] = (n + 1);
        for(int i = n; i >= 1; i--){
            sum += val[i];
            rr[i] = pre[sum] - 1;
            pre[sum] = i;
        }
        for(int i = 1; i <= n; i++){
            if(st[i] == 'A'){
                if(ll[i] >= 0 && rr[i] >= -1){
                    LL val = ((f2[i] - f2[ll[i] - 1]) - (f1[i] - f1[ll[i] - 1])) +
                             ((f1[rr[i] - 1] - f1[i - 2]) - (f2[rr[i] - 1] - f2[i - 1]));
                    ins(ll[i], rr[i], val);
                }
            }
            else ins(i - 1, i, 0ll);
        }
        dp[0] = 0ll;
        for(int i = 1; i <= n; i++) dp[i] = 1e18;
        for(int i = 0; i < n; i++){
            for(int k = las[i]; k; k = a[k].next){
                int y = a[k].y;
                dp[y] = min(dp[y], dp[i] + a[k].c);
            }
        }
        cout << dp[n] << "\n";
        len = 0;
        for(int i = 0; i <= n; i++) las[i] = 0;
    }
    
    return 0;
}

不懂啊，感觉完全不如 $BCE$ 难，奇怪的难度评价。

官方题解

好吧，官方题解确实难想。

其先基于这么一个转化：如果在原字符串后面添上 $B$ ，那么原题可以转化为：花最小的代价使得原串可以被分割成 $AB,B$ 。

那么一个观察就是 $AB$ 中的 $A$ 一定不会跨过 $B$ ，否则 $A$ 与这个 $B$ 组合一定更优。

证明要详细写出来可能会比较麻烦，大致就是讨论一下，因为最优方案一定可以写成每个 $A$ 按顺序往某个方案移动，而且 $A/B$ 与 $A/B$ 之间不会交换，根据这个原理讨论一下就行了。

由这个观察，我们可以证明，满足这个观察的最优答案一定可以分成若干段，其中 $[l_i,r_i]$ 满足两个字符串在这个区间上的 $A,B$ 数量一样，且最终字符串要么是 $B$ ，要么是 $ABABAB…AB$ ，那么就能得到下面的 $dp$ 。

设 $dp[i]$ 表示前 $i$ 个字母变成可以分割成 $AB,B$ 的字符串最小代价。

如果 $i$ 后面是 $B$ ，则可以 $dp[i]\to dp[i+1]$ 。

或者可以在后面放 $AB$ ，根据上面的条件可以得到 $dp[i]\to dp[j]+cost(i+1,j)$ ，满足 $[i+1,j]$ 中的 $A,B$ 数量一样，可以注意到，等价于 $A$ 看成 $1$ ，$B$ 看成 $-1$ 后 $s_{i}=s_{j}$ ，而且又显然，$s_{i}$ 只需要更新到后面第一个满足要求的 $j$ 就行了，因为若 $j,k$ 都满足要求的话：$cost(i+1,k)=cost(i+1,j)+cost(j+1,k)$ ，所以只需要 $i\to j\to k$ 就行了。

至于算 $cost$ 的话，注意到，每一段的 $j$ 都是往一个方向移动的，所以可以很方便的算出 $cost$ 。（原因：根据上面的 $dp$ 过程不难得到，这一段的前缀和都是同号的，要么 $>0$ ，要么 $<0$ ，除了整段是 $=0$ 的）

综上，时间复杂度：$O(n)$ 。

这个做法比我的做法难想，但是比我的做法好写。

而且其中很多思考的细节是值得认真想想的，很有意义的一个做法，感觉能想明白这个做法对提升 $dp$ 能力很有帮助。