[dp+经典问题]poj-2533-Longest Ordered Subsequence(最长上升子序列)

https://vjudge.net/problem/POJ-2533#author=karl_sc

poj天天炸 放个VJ页面吧(逃

很经典的LIS（ longest  increasing subsequence ）
说实话今天学习真的没有状态 可能是有点疲惫了？。。。
刚开始深入的学dp 那这个经典问题好好的谈一谈

我们知道dp的经典思维就是看上一个的状态 因此 最长上升子序列也就是
n的最长上升子序列也就是n-1的最长上升子序列 我也不知道我说了一句什么话 还是列公式吧
lis[i]=max(lis[j])+1(arr[j]<arr[i]) 就是说 每找到一个数 就遍历所有的数字 找到比他小且lis最大的那个数字 然后 就是那个数的lis+1
举个例子：
1 7 3 5 9 4 8
lis[1]=1;
lis[2]=1+1=2;
lis[3]=1;
lis[4]=lis[1]+1=2;
lis[5]=lis[4]+1=3;
lis[6]=lis[3]+1=2;
lis[7]=lis[3]+1=2;
lis[8]=lis[5]+1=4;
lis[9]=lis[8]+1=5;
代码很简单 但是今天很迷的状态还是写错了不少地方 好菜
分析下时间复杂度 每一个数都要便利前面所有的数字 O（n^2）无疑了

然后它A了。。。这个题数据比较水

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1005;
int lis[maxn];
int arr[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
lis[0] = 1;
int maxn = 0;
for (int i = 1; i < n; i++) {
maxn = 0;
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
maxn = max(maxn, lis[j]);
}
}
lis[i] = maxn+1;
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, lis[i]);
}
cout << ans << endl;
return 0;
}

好 那么我们知道 n2的复杂度是有点丑的
我们可以把他优化为nlogn的复杂度
来 讲讲我们下一种想法
还是那个例子 1 7 3 5 9 4 8
我们搞一个数组B
扫一遍数组
1 入 B:1
7 入 B: 1 7
3 入 B: 1 3
5 入 B: 1 3 5
9 入 B: 1 3 5 9
4 入 B: 1 3 4
8 入 B: 1 3 4 8
你看 这样B 是不是就是我们要的数组啦 但是有个疑问 这不还是扫了两边吗
等等 这个时候 我们的二分查找就来了 查找的时候用二分 n变logn
妈的心态炸了 写了这么久的Lower_bound 都是wa 找了个大佬的直接贴一下
来自：https://blog.csdn.net/aqa2037299560/article/details/82873340

明显快了

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
int i, j, n, s, t, a[100001];
int main()
{
cin >> n;
a[0] = -1000000;
for (i = 0; i < n; i++)
{
cin >> t;
if (t > a[s]) a[++s] = t;
else
{
int l = 1, h = s, m;
while (l <= h)
{
m = (l + h) / 2;
if (t > a[m]) l = m + 1;
else h = m - 1;
}
a[l] = t;
}
}
cout << s << endl;
}

还有一种树状数组的做法 这里不谈了
https://blog.csdn.net/George\_\_Yu/article/details/75896330

uncategorized > POJ
[dp+经典问题]poj-2533-Longest Ordered Subsequence(最长上升子序列)
https://47.97.0.163/2019/07/26/dp经典问题poj-2533-longest-ordered-subsequence最长上升子序列/
作者
John Doe
发布于
2019年7月26日
许可协议