CF1873G ABBC or BACB 题解

Kei__ · 2025-02-07 10:43:50 · 题解

为什么没有人用 DP？来水一发 DP 题解。

典型的线性 DP，先来考虑两个特殊情况：AAAB 和 BAAA。
第一个情况可以变为 BCCC，获得 3 枚金币。第二个情况可以变为 CCCB，获得 3 枚金币。不难发现，当出现 k 个 A 与一个 B 的组合，可通过操作一和二获得这 k 枚硬币。

我们可以通过遍历一遍字符串确定每一组连续的 A 子串的左边界，从而确定这一组的长度，用数组 l 储存下来，方便状态转移。
先建立一个 DP 数组 dp_{i,j}，表示到第 i 个字符可获得的最大金币数，j 表示是否对第 i-1 与 i 个字符形成的子串进行操作，0 表示不进行，1 表示进行。

随后分类讨论进行转移。

当第 i-1 与 i 个字符形成的子串为 AB，即可获得 i-l_{i-1} 枚金币，可以由 dp_{l_{i-1}-1,0} 或 dp_{l_{i-1}-1,1} 转换而来，从而得到转换方程：

当第 i-1 与 i 个字符形成的子串为 BA，由于 i 的限制，不能直接转移到连续 A 子串的右边界，因此只能获得一枚金币，然后用一个变量 c 记录下进行操作后第 i 个字符的变化，用于第三种情况。可得转换方程：

当 c 与 i 个字符形成的子串为 BA，表示上一次操作后可再进行一次操作，因此由 dp_{i-1,1} 转换而来，可得转换方程：

最后的答案为 \max(dp_{n,0},dp_{n,1})，其中 n 表示字符串末尾下标。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define I_love_Foccarus return
#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define int long long
const int N = 2e5 + 5;
void fast() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
string a;
int dp[N][2] , l[N];
char c;
signed main(){
    fast();
    int t;
    cin>>t;
    while(t--){
        memset(dp , 0, sizeof(dp));
        cin>>a;
        int len = a.size();
        a = " " + a;
        l[0] = 1;
        for(int i = 1 ; i <= len ; i++) l[i] = a[i] == 'A' ? l[i - 1] : i + 1;
        c = a[0];
        for(int i = 2 ; i <= len ; i++){
            if(a[i - 1] == 'A' && a[i] == 'B'){
                dp[i][1] = max(dp[l[i - 1] - 1][1] , dp[l[i - 1] - 1][0]) + i - l[i - 1];
                c = 'C';
            }else if(a[i - 1] == 'B' && a[i] == 'A'){
                dp[i][1] = dp[i - 1][0] + 1;
                c = 'B';
            }else if(c == 'B' && a[i] == 'A'){
                dp[i][1]  = dp[i - 1][1] + 1;
                c = 'B';
            }
            dp[i][0]  = max(dp[i - 1][0] , dp[i - 1][1]);
        }
        cout<<max(dp[len][0] , dp[len][1])<<'\n';
    }
    I_love_Foccarus 0;
}