线性dp-LIS题目1

解题思路

我们知道，如果两个导弹第一个飞来的比第二个飞来的低，那要两套装备。如果两个导弹高度一样或者前面的导弹比后来的导弹高度高，那只需要一套装备。现在问最少要多少套装备拦截，我们可以把问题转化成这个高度序列的最长上升子序列长度是多少，就可以得到答案。

AC Code

#include<bits/stdc++.h>usingnamespacestd;intdp[1001],n,a[1001