Luogu-P1020（导弹拦截）（DP，LIS ，二分优化)

Luogu-P1020（导弹拦截）（DP)

题意：

给n（n<=100000) 个数字，求最长不上升子序列的长度和最少的不上升子序列的个数。

分析：

第一问：

求最长不上升子序列有 O(n^2) 的做法，不过这里会超时。我们需要降低算法复杂度。

j表示最长子序列的长度，然后d[i]储存以不上升子序列长度为 i 时结尾的最大数字。

假如前 i -1 个数都已经检索完毕，已经找到了最长不上升子序列d[1]~d[j] 。

然后对于第 i 个数a[i]

如果a[i]<=d[j] 那么可以添加a[i]到当前最长不上升子序列的末尾。更新d[++j]=a[i]。
如果a[i]>d[j] 那么就要尝试把a[i]放到这个子序列中合适的位置，然后更新它。相当于是找到了以a[i]结尾的最长不上升子序列长度。

1	2	3	4	5	6	7   8

389 207 155 300 299 170 158  65

第一步

1

389

第二步

1	2

389 207

第三步

1	2	3

389	207	155

第四步（300 找到了 389 后面的位置，然后把207覆盖，这里为什么要覆盖呢？稍后解释）

1	2	3

389	300	155	

第五步

1	2	3

389	300	299

第六步

1	2	3	4

389	300	299	170

第七步

1	2	3	4	5

389	300	299	170	158

第八步

1	2	3	4	5	6

389	300	299	170	158	 65

第四步中，在原来的389 207 155序列中，如果要用 300 来做不上升子序列的结尾，那这个子序列的长度最长就是2，然后现在207在这个序列的第二个位置，所以我们应该换成更优的 300 来充当整个序列的不上升子序列长度为2 的末尾数，只有这样，才能保证最优（想一想为什么？只有当前末尾数更大，才更有可能在后面的更新中使得序列更长）。那么怎么找这个位置呢？二分。通过二分，就可以把这个算法复杂度降到nlogn。

到此，第一问的解法已经解释完毕了。

第二问：

求一个序列里面最少有多少不上升子序列等于求这个序列里最长上升子序列的长度。这句话先入为主，然后就可以利用第一问的方法反着求就可以了。

但是我们静下心来仔细想一想，我们如果用O(n^2)做，该怎么做？

可以用一个数组d，d[i]表示第 i 个拦截系统当前的能打的最大高度。然后用一个变量 num 记录当前的拦截系统的个数。每次遇到a[i]，从左到右遍历d，找到最小的j使得d[j]>=a[i]然后更新d[j] = a[i]。也就是找到一个高度最合适的拦截系统去拦截导弹。由于d数组是升序的，所以更新之后依然升序。如果不存在这样的j，那么意味着就要添加导弹d[++j] = a[i]。

咦！看到这里，你有没有觉得跟上一个问题特别相似。我们可以先检查d[num]>=a[i]是否成立，如果不成立，则需要增加拦截系统d[++num] = a[i]。如果成立，那么就需要二分找到最合适的位置去更新。

那么这个求法，是不是就是在求最长上升子序列呢？

int a[100000];

int d[100000];

int n=0;

int l,r,mid;

int main()

{

    while(cin>>a[n++]);

    int j = 0;

    d[0] = a[0];

    n--;

    for(int i=1;i<n;i++)

    {

    	if(d[j]>=a[i])

            d[++j] = a[i];

        else

        {

            l = 0;r=j;

            while(l<r)

            {

                mid = (l+r)>>1;

                if(d[mid]>=a[i]) l = mid+1;

                else r = mid;

            }

            d[l] = a[i];

        }

    }

    d[0] = a[0];

    int num = 0;

    for(int i=1;i<n;i++)

    {

    	if(d[num]<a[i])

        {

            d[++num] = a[i];continue;

        }

        l = 0;r = num;

        while(l<r)

        {

            mid = (l+r)>>1;//cout<<mid<<endl;

            if(d[mid]>=a[i]) r = mid;

            else l = mid+1;

        }

        d[r] = a[i];

    }

    cout<<j+1<<endl<<num+1<<endl;

    return 0;

}

巴特西

Luogu-P1020（导弹拦截）（DP，LIS ，二分优化)