P1020 导弹拦截 dp 树状数组维护最长升序列

题目描述

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

输入导弹依次飞来的高度（雷达给出的高度数据是

输入输出格式

输入格式：

输出格式：

输入输出样例

输入样例#1：复制

389 207 155 300 299 170 158 65

输出样例#1：复制

6
2


一开始想以 前i个和当前高度  这两个为dp转移量  dp不出来。。

第一问：求最大不上升子序列长度  （小于等于）
第二问：求最大 上升子序列      （严格大于）


有一半数据为nlogn的   写的就过了一半数据

#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s)
#define LL long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define N 65
#define inf -0x3f3f3f3f
    int dp[100001];
    int dp2[100001];
    int a[100005];
int main()
{
    int x;
    int cnt=0;
    while(RI(x)==1)a[++cnt]=x;
  rep(i,1,cnt)
  {
        dp[i]=1;
        dp2[i]=1;
  }
    int maxx=0;
    int minn=0;
    rep(i,2,cnt)
    {   
        for(int j=1;j<i;j++)
        {
            if(a[j]>=a[i])dp[i]=max(dp[i],dp[j]+1);
           maxx=max(dp[i],maxx);
            if(a[j]<a[i])dp2[i]=max(dp2[i],dp2[j]+1);
            minn=max(dp2[i],minn);
        }
    }
    cout<<maxx<<endl<<minn;

    return 0;
}

View Code

另一种非常非常巧妙的方法：

直接维护一个非升序列和一个非降序列，维护的过程就能用上面两个神奇的STL（当然非升序列的upper_bound()要重载cmp）。不多说，上代码

#include<bits/stdc++.h>
using namespace std;
int a[100005],f[100005],l[100005];
struct cmp{bool operator()(int a,int b){return a>b;}};
int main()
{
    int n=1;
    while(cin>>a[n])n++;
    n--;
    int con=1,cont=1;
    l[1]=f[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(l[cont]>=a[i])l[++cont]=a[i];
        else l[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i];
        if(f[con]<a[i])f[++con]=a[i];
        else f[lower_bound(f+1,f+con+1,a[i])-f]=a[i];
    }
    cout<<cont<<" "<<con;
    return 0;
}

View Code

树状数组：

#include<bits/stdc++.h>
using namespace std;
//input
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m);
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s)
#define LL long long
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define N 100005
#define inf -0x3f3f3f3f

int c[N];
int lowbit(int x)
{
    return x&(-x);
}

void update(int x,int v)
{
    for(int i=x;i<=N;i+=lowbit(i))
        c[i]=max(c[i],v);
}
int sum(int x)
{
    int ans=0;
    for(int i=x;i>0;i-=lowbit(i))
        ans=max(ans,c[i]);
    return ans;
}

int a[N];
int main()
{
    int x;
    int cnt=0;
    while(RI(x)==1)a[++cnt]=x;
    int ans1=0,ans2=0;
    for(int i=cnt;i>=1;i--)
    {
        int p=sum(a[i])+1;
        update( a[i],p);
        ans1=max(ans1,p);
    }
    cout<<ans1<<endl;
    CLR(c,0);
    rep(i,1,cnt)
    {
        int p=sum(a[i]-1 )+1;
        update(a[i],p);
        ans2=max(ans2,p);
    }
    cout<<ans2;
    return 0;
}

View Code

这里维护的是最大值    

类似之前有一题母牛耳聋的问题  
那里维护的是1 意为存在一个牛    那题可以方便的求出在这头牛前面有几头牛（这里要是维护1是错的。。）   
树状数组的用法非常灵活    ！！！！