问题标题: 酷町堂：5539 字符串改造

小明有一个字符串，由小写英文字母组成。
小明准备对他的字符串进行改造,改造的方法是删除字符串中间的一部分字符。小明希望改造完后，新的字符串中的相邻字符都满足左边的字符小于等于右边的字符(a< b<…< z)。
例如，对于字符串happy,小明可以删除第一个字母，变成appy,满足要求。或者小明删除第二字母，变成hppy,也满足要求。小明还有其他方法使得结果满足要求。
再如，对于字符串autumn，可以删除3个字母变成amn， 或者删除4个字母变成at。其他满足要求的方案还有很多。
小明想知道，对于一个字符串，至少要删除多少个字母能满足要求。

rt，暴力TLE，二分写炸了，求助

#include<iostream>
using namespace std;
string s;
int n,ans;
int a[100005],f[100005];
void init(){
	n=s.size();
	for(int i=1;i<=n;i++)
		a[i]=s[i-1]-'a';	
}
int main(){
	cin>>s;
	init();		
	for(int i=1;i<=n;i++){
		f[i]=1;
		for(int j=1;j<i;j++){
			if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	cout<<n-ans;
	return 0;
}

二分代码

#include<iostream>
#include<bits/stdc++.h>
#define inf (1<<25)
#define reg register
using namespace std;
string s;
int n,ans=1;
int a[100005],f[100005];
void init(){
	n=s.size();
	for(int i=1;i<=n;i++)
		a[i]=s[i-1]-'a';
	f[1]=a[1];		
}
int main(){
	cin>>s;
	init();		
	for(int i=2;i<=n;i++){
		if(f[ans]<=a[i]) f[++ans]=a[i];
		else{
			int l=1,r=ans;
            while(l<r){
                int mid=(l+r)/2;
                if(a[i]<=f[mid]) r=mid;
                else l=mid+1;
            }
            f[l]=a[i];
		}
	}
	cout<<n-ans;
	return 0;
}

汪恺恒在2021-09-06 20:26:50追加了内容

d