P1020 导弹拦截
2023-08-16 11:13:47 # OI # Problem #DP #树状数组 #二分

这是一道十分经典的DP求LIS的题

但是想要过掉ta也不是那么简单哒

题面

NOIP1999 普及组 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

389 207 155 300 299 170 158 65

样例输出 #1

6
2

提示

对于前 50%50\% 数据（NOIP 原题数据），满足导弹的个数不超过 10410^4 个。该部分数据总分共 100100 分。可使用O(n2)\mathcal O(n^2) 做法通过。
对于后 50%50\% 的数据，满足导弹的个数不超过 10510^5 个。该部分数据总分也为 100100 分。请使用 O(nlog⁡n)\mathcal O(n\log n) 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 5×1045\times 10^4。

此外本题开启 spj，每点两问，按问给分。

upd 2022.8.24\text{upd 2022.8.24}：新增加一组 Hack 数据。

求LIS

题意大概是：

第一问：让你找一个最长不上升子序列，并输出它的长度

第二问：让你找一个最长上升子序列，并输出它的长度

求LIS可以见DP中我写的代码

那么最长不上升子序列呢？

也就是倒着把LIS求一遍

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int inf=0x3f3f3f3f;
int n;
int a[N],f[N];
int lis1=-inf;
int lis2=-inf;
int main()
{
    while(cin>>a[++n]);
    n--;//读取EOF
    for(int i=n;i>=1;i--)//最长不上升子序列
    {
        f[i]=1;
        for(int j=n;j>i;j--)
        {
            if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=1;i<=n;i++) lis1=max(lis1,f[i]);
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
        }
    }
    for(int i=1;i<=n;i++) lis2=max(lis2,f[i]);//到此为止是100分
    printf("%d\n%d\n",lis1,lis2);
    return 0;
}

很显然，这段代码的复杂度是O(n2)O(n^2)的，在本题中你只能获得100100分

怎么优化呢？（题目明示O(logn)O(logn)才能过）

优化

1.树状数组优化

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5;
const int inf=0x3f3f3f3f;
int n;
int a[N],f[N];
int lis1=-inf;
int lis2=-inf;
int maxn;
int lowbit(int x) { return x & -x; }
void add(int x, int c) {
  for (int i = x; i <= maxn; i += lowbit(i)) f[i] = max(f[i], c);
}
int query(int x) {
  int res = 0;
  //求以小于等于x的数为结尾的最长不上升子序列的长度的最大值
  for (int i = x; i; i -= lowbit(i)) res = max(res, f[i]);
  return res;
}
signed main()
{
    while(cin>>a[++n])
        maxn=max(a[n],maxn);
    n--;//读取EOF
    for(int i=n;i>=1;i--)//最长不上升子序列
    {
        int q=query(a[i]);
        add(a[i],q+1);
        lis1=max(lis1,q+1);
    }
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) 
    {
        int q=query(a[i]-1);
        add(a[i],q+1);
        lis2=max(lis2,q+1);
    }
    printf("%lld\n%lld\n",lis1,lis2);
    return 0;
}

2.二分查找优化

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int z[N];
int f[N],f2[N];
int a[N];
int n;
int ef1(int l,int r,int k)//l,r为z下标，k为a中下标
{
    while(l<r)
    {
        int mid=(l+r+1)>>1;//右中位数
        if(a[z[mid]]<=a[k])
            l=mid;//l=mid,保证l永远小于，满足条件
        else r=mid-1;//缩小右区间
    }
    return l;
}
int ef2(int l,int r,int k)//l,r为z下标，k为a中下标
{
    while(l<r)
    {
        int mid=(l+r+1)>>1;//右中位数
        if(a[z[mid]]<a[k])
            l=mid;//l=mid,保证l永远小于，满足条件
        else r=mid-1;//缩小右区间
    }
    return l;
}
int lis1()//可以等于
{
    int cnt=0;
    memset(f,0,sizeof(f));
    memset(z,0,sizeof(z));
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//f[i]中为序列下标
        f[i]=max(f[i],ef1(0,cnt,i)+1);
        if(f[i]>cnt)//新序列可以加，因为保证了构造出来的序列中第i位的f[]值为i，第cnt位置的f[]的值为cnt，那么加一位
        {
            cnt++;
            z[cnt]=i;//放入第cnt位数在a中的下标
        }
        else
        {
            if(a[i]<a[z[f[i]]])//长度为f[i]的数在a中的下标，因为长度为f[i]和在z中下标为f[i]是等价的
                z[f[i]]=i;//存下标，拿比你小还比你强的来更新你
            //如果需要方案，就记录一下从哪转移过来的,在发生转移的时候记录一下pre
        }
    }
    return cnt;
}
int lis2()
{
    int cnt=0;
    memset(f,0,sizeof(f));
    memset(z,0,sizeof(z));
    for(int i=1;i<=n;i++)
    {
        f[i]=1;//f[i]中为序列下标
        f[i]=max(f[i],ef2(0,cnt,i)+1);
        if(f[i]>cnt)//新序列可以加，因为保证了构造出来的序列中第i位的f[]值为i，第cnt位置的f[]的值为cnt，那么加一位
        {
            cnt++;
            z[cnt]=i;//放入第cnt位数在a中的下标
        }
        else
        {
            if(a[i]<a[z[f[i]]])//长度为f[i]的数在a中的下标，因为长度为f[i]和在z中下标为f[i]是等价的
                z[f[i]]=i;//存下标，拿比你小还比你强的来更新你
            //如果需要方案，就记录一下从哪转移过来的,在发生转移的时候记录一下pre
        }
    }
    return cnt;
}
int main()
{
    while(cin>>a[++n]);
    n--;
    int li2=lis2();
    reverse(a+1,a+n+1);
    int li1=lis1();
    printf("%d\n%d\n",li1,li2);
    return 0;
}

相当于写了两遍，比较麻烦。

还要分别写两个二分，其实就是把小于变成小于等于了。

3.线段树优化

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,maxn,l1,l2;
int a[N],f[N];
struct segment
{
    int l,r;
    int tmax;
}tr[N<<2];
void pushup(int u)
{
    tr[u].tmax=max(tr[u<<1].tmax,tr[u<<1|1].tmax);
}
void build(int u,int l,int r)
{
    tr[u].l=l,tr[u].r=r;
    if(tr[u].l==tr[u].r)
    {
        tr[u].tmax=0;
        return;
    }
    int mid=(l+r)>>1;
    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
    pushup(u);
}
void modify(int u,int x,int v)
{
    if(tr[u].l==x&&tr[u].r==x)
    {
        tr[u].tmax=v;
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(x<=mid) modify(u<<1,x,v);
    if(x>mid) modify(u<<1|1,x,v);
    pushup(u);
}
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].tmax;
    int mid=(tr[u].l+tr[u].r)>>1;
    int ans=-1;
    if(l<=mid) ans=max(ans,query(u<<1,l,r));
    if(r>mid) ans=max(ans,query(u<<1|1,l,r));
    return ans;
}
int main()
{
    // freopen("E:/下载/P1020_21.in","r",stdin);
    while(~scanf("%d",&a[++n]))
    {
        maxn=max(a[n],maxn);
    }
    n--;
    build(1,1,maxn);
    for(int i=n;i>=1;i--)
    {
        int p=query(1,1,a[i]);
        modify(1,a[i],p+1);
        l1=max(l1,p+1);
    }
    build(1,1,maxn);
    for(int i=1;i<=n;i++)
    {
        int p;
        if(a[i]!=1) p=query(1,1,a[i]-1);
        modify(1,a[i],p+1);
        l2=max(l2,p+1);
    }
    printf("%d\n%d\n",l1,l2);
    return 0;
}

与树状数组类似，记得查询前判断是否为1！

上一页
2023-08-16 11:13:47 # OI # Problem #DP #树状数组 #二分
下一页