[DP][CDQ分治][树状数组] bzoj2244 SDOI2011 拦截导弹

题目链接

题意:

给定一个序列,每个元素有两个属性 $h$ 和 $v$ ,是导弹的高度和速度,发射的拦截炮弹第一发可以是任意的高度和速度,但是要求每一发炮弹的高度和速度都不能大于前一发。问:
1. 选取最优的发射方案的时候最多能拦截多少发导弹
2. 当有多个拦截导弹数目相同的最优方案的时候,我方会从中随机选取一种方案,现在问在这种策略下,每发炮弹能拦截到导弹的概率是多少

题解:

第一问很明显使用cdq分治加速dp转移算LIS,难点在于第二问。把LIS各个节点的转移看成图上的连边的话,可以得到一个dag,而后可以想见使用dp求出到每个点的在LIS上的路径有多少条,便可以确定随机选取的情况下每个节点被选取到的概率为 经过该点的在LIS上的路径数/所有的在LIS上的路径数 。判断一个点是否在LIS上,我们可以两端各求一次LIS,分别记为 $dpl[i] dpr[i]$ ,则如果当前节点满足 $dpl[i]+dpr[i]=\max\limits_{1\le j\le n} dpl[j]+1$ 则说明其属于某个LIS,+1是为了去除节点本身的重复计算。 为了求出经过某个点的路径数,我们可以用之前 dp求最短路必经边的方法 ,从两端分别跑一次dp,分别记录两端到某个节点的属于LIS的路径数为 $gl[i]\;gr[i]$ ,这样的话经过节点i的路径数就可以表示为 $gl[i]*gr[i]$ ,则每个点被选中的概率就可以被表示为

$$\frac{gl[i]*gr[i}{\sum_{[dpl[k]=LIS]}gl[k]}$$

这就是第二问的答案了。因为分治中每次需要对 $[l,r]$ 之间的元素暴力排序,所以复杂度会多一个 $log$ ,也就是 $\mathcal{O}(n\log{}n)$

wa点:

  • 虽然写的有点久但是没有wa点,一发yes O(∩_∩)O
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF=0x3f3f3f3f;
const int maxn=1e5+5;
const int mod=1e9+7;

struct node {
    int id,h,v;
    bool operator<(const struct node& rhs)const{
        return h<rhs.h;
    }
}ns[maxn],ps[maxn];

int n,h[maxn],v[maxn];

struct TreeArray
{
    int mxbt[maxn-2];
    double kdbt[maxn-2];//初始化都为0
    int lowbit(int k){ return k&-k;}
    void updatemax(int k,int val,double kinds){//种类数
        while(k<=n){
            if(mxbt[k] < val){
                mxbt[k]=val;
                kdbt[k]=kinds;
            }
            else if(mxbt[k] == val){
                kdbt[k]+=kinds;
            }
            k+=lowbit(k);
        }
    }
    int getpremax(int k,double &kinds){//返回mx<=k的最大长度和对应的种类数
        int ans=-1;
        kinds=0;
        while(k){
            if(mxbt[k] > ans){
                ans=mxbt[k];
                kinds=kdbt[k];
            }
            else if(mxbt[k]==ans)
                kinds+=kdbt[k];
            k-=lowbit(k);
        }
        return ans;
    }
    void en(int k){//add k的逆过程
        while(k<=n){
            mxbt[k]=0;
            kdbt[k]=0;
            k+=lowbit(k);
        }
    }
} hd;

int dpl[maxn],dpr[maxn],ca[maxn],ta[maxn];
double gl[maxn],gr[maxn];

void cdq1(int l,int r){
    int (&dp)[maxn]=dpl;
    double (&g)[maxn]=gl;
    if(l==r){
        dp[ns[l].id]=max(dp[ns[l].id],1);//if not calc then 1
        g[ns[l].id]=max(g[ns[l].id],1.0);
        return ;
    }
    int mid=(l+r)>>1,pl=l,pr=mid+1,tmpi;
    double tmpd;

    cdq1(l,mid);

    for(int i=l;i<=r;++i) ps[i]=ns[i];
    sort(ps+l,ps+mid+1);
    sort(ps+mid+1,ps+r+1);
    while(pl<=mid||pr<=r){
        if(pl<=mid&&(r<pr||ps.h<=ps[pr].h)){
            //add(ps.v,dp.id]);
            hd.updatemax(ps.v,dp.id],g.id]);
            ++pl;
        }
        else{
            //dp.id]=max(dp.id],ask(ps[pr].v)+1);
            tmpi=hd.getpremax(ps[pr].v,tmpd)+1;
            if(dp.id]<tmpi){
                dp.id]=tmpi;
                g.id]=tmpd;
            }
            else if(dp.id]==tmpi){
                g.id]+=tmpd;
            }else ;
            ++pr;
        }
    }
    for(int i=l;i<=mid;++i) hd.en(ps[i].v);

    cdq1(mid+1,r);
}

bool cmp(const node &a,const node &b){return a.h>b.h;}
void cdq2(int l,int r){
    int (&dp)[maxn]=dpr;
    double (&g)[maxn]=gr;
    if(l==r){
        dp[l]=max(dp[l],1);//if not calc then 1
        g[l]=max(g[l],1.0);
        return ;
    }
    int mid=(l+r)>>1,pl=l,pr=mid+1,tmpi;
    double tmpd;

    cdq2(l,mid);

    for(int i=l;i<=r;++i) ps[i]=ns[i];
    sort(ps+l,ps+mid+1,cmp);
    sort(ps+mid+1,ps+r+1,cmp);
    while(pl<=mid||pr<=r){
        if(pl<=mid&&(r<pr||ps.h>=ps[pr].h)){
            //add(ps.v,dp.id]);
            hd.updatemax(ps.v,dp.id],g.id]);
            ++pl;
        }
        else{
            //dp.id]=max(dp.id],ask(ps[pr].v)+1);
            tmpi=hd.getpremax(ps[pr].v,tmpd)+1;
            if(dp.id]<tmpi){
                dp.id]=tmpi;
                g.id]=tmpd;
            }
            else if(dp.id]==tmpi){
                g.id]+=tmpd;
            }else ;
            ++pr;
        }
    }
    for(int i=l;i<=mid;++i) hd.en(ps[i].v);

    cdq2(mid+1,r);
}

int hashx[maxn],cxt;
int Hashx(int x){return lower_bound(hashx+1,hashx+1+cxt,x)-hashx;}

int main(){
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&h[i],&v[i]),hashx[i]=v[i];
    sort(hashx+1,hashx+1+n);cxt=1;for(int i=2;i<=n;++i) if(hashx[i]!=hashx[cxt]) hashx[++cxt]=hashx[i];//discrete
    for(int i=1;i<=n;++i) ns[n+1-i].id=i,ns[n+1-i].h=h[i],ns[n+1-i].v=Hashx(v[i]);
    cdq1(1,n);
    for(int i=1;i<=n;++i) ns[i].id=i,ns[i].h=h[i],ns[i].v=cxt+1-Hashx(v[i]);
    cdq2(1,n);
    int ans=0;
    double fm=0.0;
    for(int i=1;i<=n;++i) ans=max(ans,dpl[i]);
    for(int i=1;i<=n;++i) if(dpl[i]==ans) fm+=gl[i];
    printf("%d\n",ans);
    for(int i=1;i<=n;++i){
        if(dpl[i]+dpr[i]-1==ans){
            printf("%.12f ",gl[i]*gr[i]/fm);
        }
        else{
            printf("0 ");
        }
    }
    return 0;
}


发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据