用二分法做导弹拦截问题

能把问题简单描述一下么？

深奥，不明白啊！

有点求答案的感觉啊

1、不写题目
2、口气太狂了

你哪个学校的？

你应该是说的这道题吧，下次麻烦记得同时贴上题目

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


 
Input  
输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。


 
Output  
输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.


 
Sample Input  
389 207 155 300 299 170 158 65

 
Sample Output  
6 2

第一问就是经典dp问题中的最长不上升序列问题，用f[i]表示第i个导弹结尾的最多能打多少个导弹，dp方程为f[i]=max(f[j])+1  (if j<i && a[j]>=a[i])

对于第二问，我刚好回顾了一下组合数学中的偏序集，当然以前本来就没看大懂。。
定义一个偏序关系对于i,j如果i<j && a[i]<a[j]则称i,j之间呈偏序关系(i<j),第二问就变成了求最小反链划分，由DilWorth定理的对偶定理可知，其数目就是最长链长度，所以第二问就是求最长上升子序列

假设导弹有n个，那么上述算法实现起来应该是O(N^2)复杂度

不过上述dp方程实现起来有个二分法优化成O(nlogn)的算法，LZ应该是问那个方法吧

我就基于求最长上升子序列讲下如何使用二分法优化：

朴素算法在求f[i]时会枚举就j in [1,i-1]范围内寻找更新f[i]的数据，如果a[j]<a[i] 且 f[j]+1>f[i]则可以更新f[i]

我们加入一个数组用b[i]表示“长度为i的上升序列结尾数中最小数“，注意这个概念有点绕，我举个例子说明一下：
a={1,3,2,4}

第一步：f[1]=1,b[1]=1
第二步: f[2]=2,b[2]=3
第三步：f[3]=2,b[2]=2  //这一步更新中b[2]由3改为了2，因为长度为2的序列有两个(1,2)和（1,3），而2<3所以取2
第四步：f[4]=3,b[3]=4

现在问题是b数组又有什么用呢？

首先我们证明一个命题：b是一个单调递增序列
反证法：如果存在i<j,b[i]>=b[j],那以b[j]结尾的长度为j的序列中取第i个，肯定是小于b[j]的，所以是矛盾的，因此b数组是单调递增的

这样，我们在求f[i]时，就可以利用二分法找出“最大的j，使得b[j]<a[i]”,则f[i]=j+1，同时b[j+i]更新

下面是核心代码

int find(int p,int Maxl)
{
    int l=0,r=Maxl,mid;
    while (l<r)
    {
        mid=(l+r)/2;
        if (b[mid]>=p) r=mid-1; else l=mid;
    }
    return l;
}

int main()
{
    int i,j,k,Maxl=0;
    f[0]=0; b[0]=0;
    for (i=1; i<=n; i++)
    {
        j=find(a[i],Maxl);    //找出最大的j，使得b[j]<a[i];
        f[i]=j+1;
        if (f[i]>Maxl) Maxl=f[i];
        if (b[f[i]]==0 || b[f[i]]>a[i]) b[f[i]]=a[i];
    }
}

[ 本帖最后由 czz5242199 于 2012-1-6 22:04 编辑 ]

抱歉，我是新手，不知道要写上程序；谢谢解答