（以“分类:序列动态规划 ==摘要== {{信息题|最长严格上升子序列|http://www.codevs.cn/problem/1576/|1|100|time=2014/11/04 21:35:54}} ==题意== 求...”为内容创建页面） |
（题解错误，折叠） |
||
| 第5行： | 第5行： | ||
求最长严格上升子序列长度。 | 求最长严格上升子序列长度。 | ||
==题解== | ==题解== | ||
| − | 在[[CodeVS/1044]]说好的，这里好好研究一下怎么愉快地做LIS。 | + | {{警告|提示|旧版本的题解和代码有明显的反例（如3 6 4 5 8就会判断成最长是3），估计是由于数据水水过的，正解建议参阅文末参考资料链接。如果想了解STL map中lower_bound和upper_bound的使用方法可以参考阅读，但是针对该问题的解决方案是错误的。}} |
| + | {{折叠|旧版本题解已折叠 | ||
| + | |在[[CodeVS/1044]]说好的，这里好好研究一下怎么愉快地做LIS。 | ||
然后- -我就用了map。 | 然后- -我就用了map。 | ||
| 第11行： | 第13行： | ||
LIS的DP方程很容易得到： | LIS的DP方程很容易得到： | ||
<pre> | <pre> | ||
| − | f[x]=f[i]+1;( | + | f[x]=f[i]+1;(其中1≤I≤x-1,a[i]是最大的小于a[x]的数） |
</pre> | </pre> | ||
最朴素的<m>O(n^2)</m>肯定没难度辣，这明显可以用map和upper_bound/lower_bound处理，用法如下： | 最朴素的<m>O(n^2)</m>肯定没难度辣，这明显可以用map和upper_bound/lower_bound处理，用法如下： | ||
<pre> | <pre> | ||
| − | map<int,int> a;//如果定义作map<int,int, greater<int> > | + | map<int,int> a;//如果定义作map<int,int, greater<int> >，以下≥、>均替换为≤、< |
(...) | (...) | ||
| − | a.lower_bound(3);// | + | a.lower_bound(3);//获得a中first≥3的第一个指针 |
a.upper_bound(3);//获得a中first>3的第一个指针 | a.upper_bound(3);//获得a中first>3的第一个指针 | ||
</pre> | </pre> | ||
| 第26行： | 第28行： | ||
然后这样的话<del>好没意思</del>不能体现出算法的精妙之处，所以窝还是去百度了下辅助数列的写法，太久没做了真的不是太好想。 | 然后这样的话<del>好没意思</del>不能体现出算法的精妙之处，所以窝还是去百度了下辅助数列的写法，太久没做了真的不是太好想。 | ||
| − | 原来是首先用一个数组dp专门记录每一次从哪一项转移过来的（就是上述方程中的dp[x] | + | 原来是首先用一个数组dp专门记录每一次从哪一项转移过来的（就是上述方程中的dp[x]＝i），然后可以发现dp是一个递增数列，可以二分查找<ref>http://www.fookwood.com/archives/749</ref>，代码就不写了，二分查找还可以用一下STL中的lower_bound（和map的略有不同）: |
<pre> | <pre> | ||
lower_bound(查找范围开始指针,查找范围结束指针,比较量,比较函数[默认less<数据类型>]) | lower_bound(查找范围开始指针,查找范围结束指针,比较量,比较函数[默认less<数据类型>]) | ||
</pre> | </pre> | ||
==代码== | ==代码== | ||
| − | + | <pre>#include<cstdio> | |
| − | + | ||
#include<map> | #include<map> | ||
#include<vector> | #include<vector> | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 最长严格上升子序列 | ★☆☆☆☆ | 答案正确 | 100 | 2014/11/04 21:35:54 | 无 |
求最长严格上升子序列长度。
| 旧版本题解已折叠
展开折叠内容
|
|---|
| 在CodeVS/1044说好的，这里好好研究一下怎么愉快地做LIS。
然后- -我就用了map。 LIS的DP方程很容易得到： f[x]=f[i]+1;(其中1≤I≤x-1,a[i]是最大的小于a[x]的数） 最朴素的 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是一个递增数列，可以二分查找[1]，代码就不写了，二分查找还可以用一下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);
}
|
CloudLunar