题解 CF877B 【Nikita and string】

· · 题解

CF 传送门。

洛谷传送门。

首先，先理解提示的意思：

如果是第一个样品（样例），弦（字符串）已经很漂亮（为标准字符串）了。

在第二个样本（样例）中，他需要删除一个 b 以使其美观（变为标准字符串）。

想法：

通过遍历输入字符串，统计出现的 a 的个数，并同时记录连续出现的 b 的最大个数。然后将两者相加得到最大美丽字符串长度。

附上 O(n) 的代码：

#include <bits/stdc++.h>
using namespace std;
int ans, d , k;//表示美丽字符串的长度、连续出现的'b'的最大个数和当前连续出现的'b'的个数。
int main() {
    char c;
    while((c = getchar()) >= 'a'){
        if (c =='a') {
            ans ++;
            if (k > 0) k --;
        } else {
            d = max(++k, d);
        }
    } 
    printf("%d",ans + d);//输出美丽字符串的长度，即ans+d。
}

应该比 dp 简单吧。