第一篇题解，好激动

· · 题解

题目解读

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

开始解题

对于如此大的数据：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;
}

第一篇题解给个赞吧！！