最长不下降子序列
最长不下降子序列
- 解决的问题：给定一个序列，求最长不下降子序列的长度（nlogn的算法没法求出具体的序列是什么）
定义：a[1..n]为原始序列，d[k]表示长度为k的不下降子序列末尾元素的最小值，len表示当前已知的最长子序列的长度。
初始化：d[1]=a[1]; len=1; （0个元素的时候特判一下）
现在我们已知最长的不下降子序列长度为1，末尾元素的最小值为a[1]，那么我们让i从2到n循环，依次求出前i个元素的最长不下降子序列的长度，循环的时候我们只需要维护好d这个数组还有len就可以了。
关键问题就是怎么维护？
可以看出我们是要用logn的复杂度维护的。实际上利用了d数组的一个性质：单调性。（长度更长了，d[k]的值是不会减小的）
考虑新进来一个元素a[i]：
如果这个元素大于等于d[len]，直接让d[len+1]=a[i]，然后len++。这个很好理解，当前最长的长度变成了len+1，而且d数组也添加了一个元素。
如果这个元素小于d[len]呢？说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。
准确的说，并不是接在谁后面。而是替换掉谁。因为它接在前面的谁后面都是没有意义的，再接也超不过最长的len，所以是替换掉别人。那么替换掉谁呢？就是替换掉那个最该被它替换的那个。也就是在d数组中第一个大于它的。第一个意味着前面的都小于等于它。假设第一个大于它的是d[j]，说明d[1..j-1]都小于等于它，那么它完全可以接上d[j-1]然后生成一个长度为j的不下降子序列，而且这个子序列比当前的d[j]这个子序列更有潜力（因为这个数比d[j]小）。所以就替换掉它就行了，也就是d[j]=a[i]。其实这个位置也是它唯一能够替换的位置（前面的替了不满足d[k]最小值的定义，后面替换了不满足不下降序列）
至于第一个大于它的怎么找: STL upper_bound。每次复杂度logn。
至此，我们就神奇的解决了这个问题。按照这个思路，如果需要求严格递增的子序列怎么办？
仍然考虑新进来一个元素a[i]：
如果这个元素大于d[len]，直接让d[len+1]=a[i]，然后len++。这个很好理解，当前最长的长度变成了len+1，而且d数组也添加了一个元素。 如果这个元素等于d[len]，那么可以保证d[1..len-1]都是小于a[i]的（根据上面的证明），因此这个元素就没有什么意义了，直接忽略就好，因为它无法接在任何一个元素d后面产生一个更有优势的子序列。
如果这个元素小于d[len]，那么就在d数组中找到第一个大于等于它的元素（这个元素必然存在，至少d[len]就是），把这个元素替换成a[i]即可。
实际上可以发现，小于等于的时候可以统一按照lower_bound替换的方式来处理。
void add(int k){
if (k>=f[top]){
top++;
f[top]=k;
}else{
int l=1,r=top,mid,tan;
while (l<=r){
mid=(l+r)/2;
if (f[mid]>k){
tan=mid;
r=mid-1;
}else{
l=mid+1;
}
} //二分查找,可以用upper_bound代替,建议自己手写,反正代码不难
f[tan]=k;
}
}如何打印这个序列: 只需要加一个C[]数来存a[i]前所接的深度,倒着扫描输出深度为前一个-1的数字
#include <bits/stdc++.h>
using namespace std;
int n,a[100005],t[100005],top,c[100005];
void add(int i){
int x=a[i];
if (x>t[top]){
top++;
t[top]=x;
c[i]=top;
}else{
int l=1,r=top,mid,ans;
while (l<=r){
mid=(l+r)/2;
if (t[mid]>=x){
ans=mid;
r=mid-1;
}else l=mid+1;
}
c[i]=ans;
t[ans]=x;
}
}
int main(){
// freopen("robot.in","r",stdin);
// freopen("robot.out","w",stdout);
stack <int> s;
cin>>n;
t[0]=-1;
for (int i=1;i<=n;++i) scanf("%d",&a[i]);
for (int i=1;i<=n;++i){
add(i);
}
cout<<top<<endl;
for (int i=n;i>=1;--i){
if (c[i]==top){
s.push(a[i]); //因为要正着输出,所以用到栈
top--;
}
}
while (!s.empty()){
printf("%d ",s.top());
s.pop();
}
return 0;
}最长上升子序列
只要在最长不下降子序列上稍作修改即可
void add2(int k){
if (k>f2[top2]){ //这里改一下
top2++;
f2[top2]=k;
}else{
int l=0,r=top2,mid,tan;
while (l<=r){
mid=(l+r)/2;
if (f2[mid]>=k){ //判断条件改一下
tan=mid;
r=mid-1;
}else{
l=mid+1;
}
}
f2[tan]=k;
}
}例题
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是 ≤50000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出格式
输入格式：
1 行，若干个整数（个数 ≤100000 ）
输出格式：
2 行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入输出样例
输入样例#1：
389 207 155 300 299 170 158 65输出样例#1：
6
2思路
- 第一问直接倒着扫,求出最长不下降子序列
- 第二问正着扫,求出最长上升子序列
2.1 因为每一套系统各自独立,如果i~j之间存在k使得a[i]<a[k]则必须增加一套系统
2.2 有如下定理: 一个序列中,不上升子序列的最小覆盖数等于序列中最长上升子序列的长度
代码
#include <bits/stdc++.h>
using namespace std;
int a[100005],top=0,f[100005],top2=0,f2[100005];
void add(int k){
if (k>=f[top]){
top++;
f[top]=k;
}else{
int l=1,r=top,mid,tan;
while (l<=r){
mid=(l+r)/2;
if (f[mid]>k){
tan=mid;
r=mid-1;
}else{
l=mid+1;
}
}
f[tan]=k;
}
}
void add2(int k){
if (k>f2[top2]){
top2++;
f2[top2]=k;
}else if (k==f2[top2]){
}else{
int l=0,r=top2,mid,tan;
while (l<=r){
mid=(l+r)/2;
if (f2[mid]>=k){
tan=mid;
r=mid-1;
}else{
l=mid+1;
}
}
f2[tan]=k;
}
}
int main(){
int n=1;
while (scanf("%d",&a[n])!=EOF) n++;
n--;
for (int i=n;i>=1;--i){
add(a[i]);
}
for (int i=1;i<=n;++i){
add2(a[i]);
}
cout<<top<<endl<<top2;
return 0;
}
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/4/
