题意:给出长度为n的序列,问序列的最少能分成几个LIS。
解法:解法参考http://kmjp.hatenablog.jp/entry/2019/07/20/0900这位日本选手的。思路有一点儿像nlogn求LIS的方法。
用multiset存了当目前为止,把前i个元素分成了size个LIS且,且每个LIS的结尾元素尽量小的结尾元素。那么每次新进来一个a[i]我们就要考虑把这个a[i]分到哪一个LIS且还要保证每个LIS的结尾元素尽量小。所以就在multiset上二分一个比a[i]小且最大的元素,然后a[i]去替换它作为那个LIS新的结尾。这样就能满足上诉条件。
这个解法比较巧妙,不妨来思考下它和nlogn求LIS的解法的联系。此题解法因为重点关注了让每一个a[i]都有家可归且让每个LIS结尾元素尽量小的条件,所以也就丢失了LIS的长度信息。而LIS重点关注了LIS长度且让每个长度LIS的结尾尽量小所以丢失了让每个a[i]有家可归的信息。
代价参考上面那位日本选手的,十分简洁。
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,a[N]; multiset<int> S; int main() { cin>>n; for (int i=1;i<=n;i++) scanf("%d",&a[i]); S.clear(); for (int i=1;i<=n;i++) { auto it=S.lower_bound(a[i]); //查找第一个大于等于a[i]的值 if (it!=S.begin()) S.erase(--it); //(--it)就是小于a[i]且最大的值,a[i]将会替换它 S.insert(a[i]); } cout<<S.size()<<endl; return 0; }