C. Remove Adjacent
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
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 (sisi) if at least one of its adjacent characters is the previous letter in the Latin alphabet for sisi. 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≤i≤|s|1≤i≤|s| during each operation.
For the character sisi adjacent characters are si−1si−1 and si+1si+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.
Your task is to find the maximum possible number of characters you can remove if you choose the sequence of operations optimally.
Input
The first line of the input contains one integer |s||s| (1≤|s|≤1001≤|s|≤100) — the length of ss.
The second line of the input contains one string ss consisting of |s||s| lowercase Latin letters.
Output
Print one integer — the maximum possible number of characters you can remove if you choose the sequence of moves optimally.
Examples
input
Copy
8
bacabcab
output
Copy
4
input
Copy
4
bcda
output
Copy
3
input
Copy
6
abbbbb
output
Copy
5
Note
The first example is described in the problem statement. Note that the sequence of moves provided in the statement is not the only, but it can be shown that the maximum possible answer to this test is 44.
In the second example, you can remove all but one character of ss. The only possible answer follows.
题意:给定一个字符串,若字符串中的某个字符的前一个或者后一个是其字典序的前一个字母就可以去掉这个字符,问最多能去掉多少个字符
思路:贪心,每次去掉可以去掉字符的最大字典序的字母,可以脑补一下,如果每次都不去掉当前可以去掉的最大字典序的字母,有可能会导致策略不优,很明显嘛,比如4 bcda,你先去掉c,那么就是bda,只有1,而答案是3,这个需要多想想,其实也很显然的
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
x=0;char ch=getchar();ll f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
string s,ans[105];
int main()
{
cin>>n>>s;
ll tot=1,cnt=0;
ans[tot]=s;
while(1)
{
vector<char>v;
for(rg i=0;ans[tot][i];i++)
{
if(i==0)
{
if(ans[tot][i]-ans[tot][i+1]==1)v.push_back(ans[tot][i]);
continue;
}
if(i==ans[tot].length()-1)
{
if(ans[tot][i]-ans[tot][i-1]==1)v.push_back(ans[tot][i]);
continue;
}
if((ans[tot][i]-ans[tot][i-1]==1)||(ans[tot][i]-ans[tot][i+1]==1))v.push_back(ans[tot][i]);
}
//cout<<ans[tot]<<endl;
if(!v.size())break;
else
{
sort(v.begin(),v.end());
char ansc=v[v.size()-1];
ll flag=0;
for(rg i=0;ans[tot][i];i++)
{
if(ans[tot][i]==ansc&&!flag&&((ans[tot][i]-ans[tot][i-1]==1)||(ans[tot][i]-ans[tot][i+1]==1)))
{
flag=1;
continue;
}
else ans[tot+1]+=ans[tot][i];
}
}
tot++;
//cout<<ans[tot]<<endl;
cnt++;
}
cout<<cnt<<endl;
// while(1)getchar();
return 0;
}
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有