游园安排--最长上升子序列+输出序列

1.最长上升子序列，用二分+贪心算法优化的那个

2.分割提取游客名字，与蓝肽子序列类似

3.关键是我不知道怎么输出答案序列，这里学习了一种不按序实现的，思想是倒序能凑上就加入，反正从ma开始遍历，生成一定是答案之一

P8736 [蓝桥杯 2020 国 B] 游园安排 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
string s;
int l[N],n;
string g[N];
string an[N];
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);vector<string> a;cin>>s;string b;for(int i=0;i<s.size();i++)///分割提取游客名字 {if(s[i]>='A'&&s[i]<='Z'){if(b!="")a.push_back(b);b="";b.insert(b.end(),s[i]);}else b.insert(b.end(),s[i]);}if(b!="")a.push_back(b);n=a.size();for(int i=0;i<n;i++) g[i]="zzzzzzzzzzzzzzzzz";int cl=0;for(int i=0;i<n;i++){int p=lower_bound(g,g+n,a[i])-g;///用二分贪心实现的最长上升子序列算法 g[p]=a[i];l[i]=p+1;cl=max(p+1,cl);}int x=0;for(int i=n-1;i>=0;i--)///倒序输出最长上升子序列 ///主打一个能凑成就行///因为可能有多个，而题目要求输出字典序最小的///这个做不到，但是容易理解 {if(l[i]==cl){an[x++]=a[i];cl--;}}for(int i=x-1;i>=0;i--) cout<<an[i];return 0;
}