LIS_续
LIS的二分做法
首先来看看一个序列 1 3 5 4 6 8 2
按照之前的滑动窗口的处理思路，你在一个元素入队之前判断他和队顶元素的大小譬如队列是1 3 现在你来一个2，你会发现把2替换3，这样的排列1 2可以给后面的元素提供更大的入度
你单独只放1 3后面假如再来个3就无法入队了，但是1 2的话3就可以进去，这样的话此时的LIS就是最优的，每次我们都从已入队元素中找到第一个大于等于他的元素，然后用当前元素替换他。如果他比队尾元素还大就直接放入队尾
但是要注意 1 3 5 4 6 8 2，假设B数组是储存LIS最小优的数组，len就是LIS
遇到1， B={1} len=1
遇到3， B={1,3} len=2
遇到5， B={1,3,5} len=3
遇到4， B={1,3,4} len=3
遇到6， B={1,3,4,6} len=4
遇到8， B={1,3,4,6,8} len=5
遇到2， B={1,2,4,6,8} len=5可以发现此时的B不是真正的LIS序列，他只是保证单项入度最优，并不影响LIS
luoguP1020
第一问，导弹高度不大于之前的导弹高度，所以就是一个非上升连续子序列，也就是a[i]>=a[j] (i>j)
第二问，一套导弹只能拦截他之后高度比它小的，也就意味着后面比他高的就无法拦截，仔细想想就是求LIS
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+7;
#define ll long long
int a[maxn];
int dp_1[maxn];///LIS
int dp_2[maxn];///最长非上升子序列
int n=0;
int main()
{
int x;
while(scanf("%d",&x)!=EOF)
{
a[++n]=x;
}
int ans_1=0;
int ans_2=0;
memset(dp_1,0,sizeof (dp_1));
memset(dp_2,0,sizeof (dp_2));
for (int i=1;i<=n;++i)
{
dp_1[i]=1;
for (int j=1;j<i;++j)///找寻之前的是否可以合并
{
if (a[i]>a[j])
{
ans_1 = max(ans_1,dp_1[i]=max(dp_1[i],dp_1[j]+1));
}
}
ans_1=max(ans_1,dp_1[i]);///判断是否加入原来的子序列，否则直接以a[i]单独创建一个子序列
}
for (int i=n;i>=1;--i)///仔细理解后就会发现就是反向跑一遍lis
{
dp_2[i]=1;
for (int j=i+1;j<=n;++j)
{
if (a[i]>=a[j])///记得加上等于
{
ans_2 = max(ans_2,dp_2[i]=max(dp_2[i],dp_2[j]+1));
}
}
ans_2=max(ans_2,dp_2[i]);
}
printf("%d\n%d\n",ans_2,ans_1);
return 0;
}
O（n^2)的复杂度过了一半
看看二分的
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+7;
const int INF=0x3f3f3f3f;
#define ll long long
int B[maxn];///入队LIS数组
int A[maxn];///原数组
int C[maxn];///最长非上升子序列数组
int n=0;
int A_search(int r,int x){///>
int mid,l=1;
while (l<=r){
mid=(l-r)/2+r;
if (B[mid]<x)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return l;///最后满足就是刚好小于
}
int B_search(int r,int x){///>=
int mid,l=1;
while (l<=r){
mid=(l-r)/2+r;
if (C[mid]<=x)
{
l=mid+1;
}
else
{
r=mid-1;
}
}
return l;
}
int main()
{
while(EOF!=scanf("%d",&A[++n])){
}--n;
int lis=1;
B[1]=A[1];
for (int i=2;i<=n;++i){
if (A[i]>B[lis]){///如果当前比入队的最大值还大就直接入队
B[++lis]=A[i];
}
else {
int t= A_search(lis,A[i]);///找到第一个大于等于A[i]的元素位置
B[t]=A[i];///替换
}
}
int ans=1;
C[1]=A[n];///倒序
for (int i=n-1;i>=1;--i){///反向查询
if (A[i]>=C[ans]){///如果当前比入队的最大值还大或者等于就直接入队
C[++ans]=A[i];
}
else {///由于等于的也可以入队，所以查找时直接就查找大于的位置
int t= B_search(ans,A[i]);///找到第一个大于A[i]的元素位置
C[t]=A[i];///替换
// cout<<t<<endl;
}
}
printf("%d\n%d\n",ans,lis);
return 0;
}
当然你也会发现直接找位置就不必判断了，所以选择lowerbound和upperbound
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+7;
const int INF=0x3f3f3f3f;
#define ll long long
int n=0;
int a[maxn];///储存原数组
int b[maxn];///储存长度
int c[maxn];///储存当前最小子数组LIS
int d[maxn];///储存长度
int f[maxn];///储存当前最小子数组，非上升子序列
int main()
{
while (scanf("%d",&a[n])!=EOF)
{
++n;
}
fill(c,c+n,INF);
fill(d,d+n,INF);///由于是要直接得到位置，则最后超过实际的查询长度遇到INF就截止了
int maxx_1=-INF;
for (int i=0;i<n;++i)
{
int j=lower_bound(c,c+n,a[i])-c;///减去本身得到位置
b[i]=j+1;
maxx_1=max(b[i],maxx_1);
c[j]=a[i];///直接取代
}
int maxx_2=-INF;
for (int i=n-1;i>=0;--i)
{
int j=upper_bound(d,d+n,a[i])-d;///由于等于号也算进去，此时只要找到最大位置即可
f[i]=j+1;
maxx_2=max(f[i],maxx_2);
d[j]=a[i];
}
printf("%d\n%d\n",maxx_2,maxx_1);
return 0;
}