(以“分类:序列动态规划 ==摘要== {{信息题|最长严格上升子序列|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;(其中1<=i<=x-1,a[i]是最大的小于a[x]的数)
+
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中first>=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]=i),然后可以发现dp是一个递增数列,可以二分查找<ref>http://www.fookwood.com/archives/749</ref>,代码就不写了,二分查找还可以用一下STL中的lower_bound(和map的略有不同):
+
原来是首先用一个数组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>
 
==代码==
 
==代码==
{{折叠|1576.cpp代码已折叠
+
<pre>#include<cstdio>
|<pre>#include<cstdio>
+
 
#include<map>
 
#include<map>
 
#include<vector>
 
#include<vector>

2015年10月11日 (日) 01:42的最后版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
最长严格上升子序列 ★☆☆☆☆ 答案正确 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]的数)

最朴素的O(n^2)肯定没难度辣,这明显可以用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是一个递增数列,可以二分查找[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);
}

参考资料

  1. http://www.fookwood.com/archives/749

著作权声明[编辑]

关于[编辑]