P1020 [NOIP1999 普及组] 导弹拦截

题目

题目链接

题解

看了网上好多讲解的博客，都好屑啊。

就当已知第一问求解最长不上升子序列长度，第二问求解最长上升子序列长度。

如果想知道证明，可以自行百度Dilworth定理，或者参考这个博客。

未优化（O(n2)）

未优化的比较基础。

第一问

状态定义：dp[i]表示以第i个数结尾的不上升子序列的长度。 状态转移：如果a[i] b;}

第一问

先思考一下时间都浪费在了哪里？

遍历第i个数之前的所有数时，很显然会将某个子序列中的全部数都遍历一遍，并且还会尝试一下是否能添加到每一个数的后面，但其实只需要判断第i个数是否不超过子序列的最后一个数即可，如果没超过则将第i个数添加该子序列的末尾，如果超过则不对该子序列操作。所以，如此看来，只需要遍历每个序列的最后一个数，让第i个数与之进行比较即可。

考虑一下最坏的情况，即整个序列按升序排列，每个数自成一个序列，遍历到第i个数时还是要扫描之前全部的数，所以时间复杂度为 O ( n ( n − 1 ) 2 ) O(\frac{n(n-1)}{2}) O(2n(n−1)​)，这不还是 O ( n 2 ) O(n^2) O(n2)嘛。

考虑能不能贪心一下，只动态保存每个长度下不上升子序列末尾元素的最大值。 比如，比较全部长度为1的不上升子序列的最后一个数，取最大值作为d[1]；比较全部长度为2的不上升子序列的最后一个数，取最大值作为d[2]……。

之所以选取“最大的最后一个数”，这是因为序列的最后一个数决定着后续是否可以继续添加数字，贪心地思考，如果保证最后一个数字尽可能大，那么后续能添加的数也就会尽可能多，子序列也就会尽可能的长。

完整地定义一遍，d[len]表示长度为len的不上升子序列中最后一个数的最大值。

从合理性的角度分析，很显然，d数组是降序的，即d[1]>=d[2]>=d[3]……。 举个例子，如果全部长度为2的子序列最后一个数的最大值大于了全部长度为1的子序列最后一个数的最大值，就说明长度为2的子序列中包含了一个大的数，而长度为1的子序列中居然没包含这个大的数，这很显然与我们的贪心思路不符啊，长度为1的子序列明明也可以去选择大的数，但是却偏偏选了小的数，这不合理吧。所以，很显然d[1]>=d[2]，其他同理。

如何更新d[len]？

① 遍历到的第i个数值为a[i]，如果a[i] d[已遍历的数构成的不上升子序列的最长长度]，则说明第i个数不能用于扩展当前构成的最长不上升子序列，但是因为我们要贪心，所以可以用于更新其他长度下的d值，让其他长度的d值尽可能大。更新的思路为，对于降序数组d，要找到第一个小于a[i]的数所在索引idx，将d[idx]的值替换为a[i]，表示长度为idx的子序列的最后一个数的最大值现在改为a[i]了。

举个例子解释一下。 假设遍历到了第i个数a[i]，d数组的状态如下，此时len=6，len表示d数组的有效长度，即已遍历的数构成的最长不上升子序列的长度，接下来要通过a[i]更新d数组。

  i		1	2	3	4	5	6
d[i]   10	8	7	7	6	5

CASE1：如果a[i] = 5，则由于只要满足“不上升”就可以添加，a[i] d[len]，所以进行②，找到第一个小于a[i]的位置即d[5]，替换d[5]=a[i]，d数组更新后如下。

  i		1	2	3	4	5	6
d[i]   10	8	7	7	7	5

几个细节问题：

1. 为什么更新的时候，选择的是“小于的”而不是“小于等于的”？

   就像上面举的例子，如果替换第一个小于等于的数，则替换d[3]=a[i]，d数组没有实质性的改变，没起到贪心的效果。本质上是因为允许非严格的升序，即连续的两个值可以相等。

2. 为什么更新的时候，选择的是“第一个”，不能更新其他的吗？

   首先为什么更新第一个，你要是更新了第二个，那d还是递减的吗！

3. 为什么更新的时候，不是将小于a[i]的全部d值都更新了，而是只更新第一个？

   首先，都更新了，d就变成了：

     i		1	2	3	4	5	6
   d[i]   10	8	7	7	7	7
   

   单看着就很奇怪。

   如果严谨点说，因为d数组只保存的末尾最大数，并没有保存该最大数在哪个子序列中，也就是说我们并不知道d[1]=10与d[2]=8是否处于同一个序列。同样地，我们也并不知道d[5]=6和d[6]=5是否处于同一个序列d[5]=6和d[6]=5可能表示的是同一个序列。这样一来，如果要是用a[i]=7更新d[5]和d[6]必须保证d[5]和d[6]表示的不是同一个序列才行，因为一个数在一个序列中只能用一次，所以为了避免这种歧义的产生，我们就只更新“第一个”，而不更新全部。

4. 对于第一个小于的数的查询，可以使用upper_bound函数。

第二问

第二问如出一辙。

同样的道理，只不过这一问是求“最长上升子序列”的长度，所以存在以下几点不同：

① 贪心思路为d中的值尽可能小；

② d数组是严格升序的；

③ 添加a[i]的条件为d[已遍历的数构成的上升子序列的最长长度] < a[i]；

④ 替换的方式为用a[i]替换第一个大于等于a[i]的d值。

因为要保证d是严格升序，就必须使用lower_bound，即大于等于。 使用lower_bound，如果找到的数等于a[i]，则用a[i]替换之，相当于没有进行实质性改变，依旧保证严格升序；如果找到的数大于a[i]，则用a[i]替换之，依旧保证严格升序。

O(n2) 代码

#include
using namespace std;
const int N = 50005;

int a[N], dp[N], tot, ans1, ans2;

int main()
{
	while (cin >> a[++tot]) ; // 注意会多输入一个0 
	
	for (int i = 1;i