自动搬运

查看原文

来自洛谷，原作者为

	qzmoot 唯有残生相思入骨，我的爱一如既往，至死不渝

搬运于2025-08-24 22:41:56，当前版本为作者最后更新于2023-07-12 09:59:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目解读

输入一个字符串，大写开头的是人名，要求输出这个字符串的最长上升子序列。

开始解题

对于如此大的数据：$10^6$ 用 $O(n^2)$ 的做法肯定会 TLE 所以我们考虑用二分优化。

对于二分，我们可以使用 lower_bound 函数，就是下界判断 lower_bound(a.begin(),a.end(),value) 就是当查找到的值: $mid<value$ 时就会继续，$mid\geq value$ 时返回。

由次我们就可以查找到数组中最小的数进行替换。

代码

#include <bits/stdc++.h>
using namespace std;
string a,dp[1000005],s[1000005],ans[1000005];
int h=0,t=0,cnt=1,idx=1,len=0;
int main()
{
	cin>>a;
	for(int i=0;i<a.size();i++)
	{
		if(isupper(a[i]))
			s[++cnt]=a[i];
		else
			s[cnt]+=a[i];
	}
	for(int i=1;i<=cnt;i++)
	{
		int pos=int(lower_bound(dp+1,dp+len+1,s[i])-dp);
		len=max(len,pos);
		dp[pos]=s[i];
		ans[pos]=ans[pos-1]+s[i];
	}
	cout<<ans[len];
    return 0;
}

第一篇题解给个赞吧！！