CodeVS/1576

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
最长严格上升子序列	★☆☆☆☆	答案正确	100	2014/11/04 21:35:54	无

题意

求最长严格上升子序列长度。

题解

提示
旧版本的题解和代码有明显的反例（如3 6 4 5 8就会判断成最长是3），估计是由于数据水水过的，正解建议参阅文末参考资料链接。如果想了解STL map中lower_bound和upper_bound的使用方法可以参考阅读，但是针对该问题的解决方案是错误的。

旧版本题解已折叠 展开折叠内容

在CodeVS/1044说好的，这里好好研究一下怎么愉快地做LIS。 然后- -我就用了map。 LIS的DP方程很容易得到： f[x]=f[i]+1;(其中1≤I≤x-1,a[i]是最大的小于a[x]的数） 最朴素的肯定没难度辣，这明显可以用map和upper_bound/lower_bound处理，用法如下： map<int,int> a;//如果定义作map<int,int, greater<int> >，以下≥、>均替换为≤、< (...) a.lower_bound(3);//获得a中first≥3的第一个指针 a.upper_bound(3);//获得a中first>3的第一个指针 于是很容易就用标准库得到答案了。 然后这样的话好没意思不能体现出算法的精妙之处，所以窝还是去百度了下辅助数列的写法，太久没做了真的不是太好想。 原来是首先用一个数组dp专门记录每一次从哪一项转移过来的（就是上述方程中的dp[x]＝i），然后可以发现dp是一个递增数列，可以二分查找，代码就不写了，二分查找还可以用一下STL中的lower_bound（和map的略有不同）: lower_bound(查找范围开始指针,查找范围结束指针,比较量,比较函数[默认less<数据类型>]) 代码 #include<cstdio> #include<map> #include<vector> #include<algorithm> using namespace std; map<int,int,greater<int> > f; int n,a,Ans=0; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&a); if(f.upper_bound(a)!=f.end()) f[a]=f.upper_bound(a)->second+1; else f[a]=1; Ans=max(Ans,f[a]); } printf("%d",Ans); }