CF1321C Remove Adjacent（周围串删除）（贪心算法）

You are given a string ss consisting of lowercase Latin letters. Let the length of ss be |s|∣s∣ . You may perform several operations on this string.

In one operation, you can choose some index ii and remove the ii -th character of ss ( s_isi ) if at least one of its adjacent characters is the previous letter in the Latin alphabet for s_isi . For example, the previous letter for b is a, the previous letter for s is r, the letter a has no previous letters. Note that after each removal the length of the string decreases by one. So, the index ii should satisfy the condition 1 \le i \le |s|1≤i≤∣s∣ during each operation.

For the character s_isi adjacent characters are s_{i-1}si−1 and s_{i+1}si+1 . The first and the last characters of ss both have only one adjacent character (unless |s| = 1∣s∣=1 ).

Consider the following example. Let s=s= bacabcab.

1. During the first move, you can remove the first character s_1=s1= b because s_2=s2= a. Then the string becomes s=s= acabcab.
2. During the second move, you can remove the fifth character s_5=s5= c because s_4=s4= b. Then the string becomes s=s= acabab.
3. During the third move, you can remove the sixth character s_6=s6= 'b' because s_5=s5= a. Then the string becomes s=s= acaba.
4. During the fourth move, the only character you can remove is s_4=s4= b, because s_3=s3= a (or s_5=s5= a). The string becomes s=s= acaa and you cannot do anything with it.

Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.

输入格式

The first line of the input contains one integer |s|∣s∣ ( 1 \le |s| \le 1001≤∣s∣≤100 ) — the length of ss .

The second line of the input contains one string ss consisting of |s|∣s∣ lowercase Latin letters.

输出格式

Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.

题意翻译

给出字符串 s ， 1≤∣s∣≤100 。

定义一次变换为，选中第 i 个字符移除，字符串长度减少  1，选中字符需要满足 si−1,si+1 中至少有一个是  si 的前驱。

求最多可进行几次操作。

输入输出样例

输入

8

bacabcab

输出  

4

输入  

4

bcda

输出  

3

输入  

6

abbbbb

输出  

5

分析我们可以用string来做，我们先从z字符开始进行搜索删除，然后我们在一次一次的从新搜索，最后就是答案，具体实现看代码。

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  string s;
  cin>>n>>s;
  for(int i='z';i>'a';i--) //从z开始删 
    for(int j=0;j<s.size();j++)
      if(s[j]==i&&(j>0&&s[j-1]==i-1 || j<s.length()-1&&s[j+1]==i-1))//要注意不能越界
        s.erase(j,1),j=-1;//erase(j,n); 删除从j开始的n个字符，比如erase(0,1)就是删除第一个字符j=-1,是为了从头开始遍历。 
  cout<<n-s.size()<<endl;
}