#P12341. [蓝桥杯 2025 省 A/Python B 第二场] 消消乐

    ID: 13977 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 2 上传者: 标签>贪心2025双指针 two-pointer蓝桥杯省赛

[蓝桥杯 2025 省 A/Python B 第二场] 消消乐

题目描述

小蓝正在玩一个叫“一维消消乐”的游戏。游戏初始时给出一个长度为 nn 的字符串 S=S0S1Sn1S = S_0S_1\ldots S_{n-1},字符串只包含字符 A\text{A}B\text{B}。小蓝可以对这个字符串进行若干次操作,每次操作可以选择两个下标 i,j[0,n1]i, j \in [0, n-1],如果 i<ji < jSi=AS_i = \text{A}Sj=BS_j = \text{B},小蓝就可以把它们同时消掉。小蓝想知道在经过若干次操作后,直到无法对字符串继续进行操作时,字符串最多剩下多少个字符。

输入格式

输入一行包含一个长度为 nn 的字符串 SS

输出格式

输出一行包含一个整数表示答案。

BABAABBA
4

提示

样例说明

先消掉 (S1,S6)(S_1, S_6),再消掉 (S4,S5)(S_4, S_5),此时剩下 BBAA\text{BBAA},无法继续进行操作。

评测用例规模与约定

  • 对于 10%10\% 的评测用例,1n201 \leq n \leq 20
  • 对于 20%20\% 的评测用例,1n1001 \leq n \leq 100
  • 对于 50%50\% 的评测用例,1n100001 \leq n \leq 10000
  • 对于所有评测用例,1n1061 \leq n \leq 10^6