赞
踩
受启发于:https://www.cnblogs.com/wxjor/p/5524447.html
在学习DP时相信我们都遇到过这一道题:最长上升子序列,这道题用DP来解的话时间复杂度为n^2;
这在n大概是10000,而时间限制为1秒时是可以被接受的,但是当n取到100000时我们就不能只用简单的DP来做了
这个时候我们可以使用另一种DP,那就是对长度DP
我们建立一个数组DP[100001];
DP[i]表示能使上升序列长度为i时的所有序列中的最右边的数字的最小值
比如序列 2 3 4 1 5 8 6,很显然,最长上升子序列长度为5,分别为 2 3 4 5 6或者 2 3 4 5 8
那么DP[1…5]={1 3 4 5 6}
因为长度为1时,我们可以取任意数当序列,所以很明显1是最小的,所以DP[1]=1。
当长度为2时,我们可以取的序列有 {2,3} {2,4} {2,5},{2,8}…等等,很明显所有序列中的最右边的数字的最小值为3,所以DP[2]=3;
依次类推
这个数列有什么用呢
如果我们已经有了这个DP数列,我得到了一个新数字我该怎么处理呢,比如10
很明显,如果它比6大,说明,我们可以得到序列 2 3 4 5 6 10,所以我们就可以将答案和DP数组的长度更新为6,同时DP[6]=10
既DP[1…6]={1 3 4 5 6 10}
依次类推
但是如果我们得到一个新数字不能比DP最右边的数字大呢,比如这个数字是2的时候, 我们该怎么办呢,
我们当然不能忽略这个数字,当它等于2的时候,我们可以知道,我们可以得到上升序列为{1 2},所以DP[2]应该等于2才对
所以我们就可以更新DP数列DP[1…6]={1 3 4 5 6 10},更新为DP[1…6]={1 2 4 5 6 10}
那有人会问,我们更新DP数列有什么用?
那是肯定有用啊 ,因为我们通过不断的更新以后,我们会把DP数组元素变得尽可能地小,导致我们可能会把最右边的数字更新得更小,使得增加长度更容易,这很棒不是吗?
比如说来了一个新的数字9的话,它比10小,那么我们就可以把10更新为9,既DP[1…6]={1 2 4 5 6 9}
增加的方法很容易,那我们的更新方法是什么?
最重要的来了:
最重要的来了:
最重要的来了:
我们更新DP数组的方法是从从到右找到第一个比他大的数字,然后把它替换掉
如果我们傻傻地从左往右找,时间复杂度仍然为n^2,欧,功亏一篑
一拍脑袋,既然DP数组是有序递增的,那么我们为什么不使用二分查找呢
所以,我们将上面的步骤用代码表示出来的时候是这样的:
#include <iostream> #include <algorithm> using namespace std; const int maxn = 2e6 + 1; int dp[maxn]; int main() { int n,num,ans = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> num; if (i == 1 || num > dp[ans - 1]) { dp[ans] = num; ans++; } else { auto q = lower_bound(dp, dp + ans + 1,num); *q = num; } } cout << ans << endl; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。