[LIS&LDS详解]导弹拦截——洛谷-P1020 [LIS&LDS详解]导弹拦截——洛谷

传送门导弹拦截
先介绍一下lower_bound和upper_bound； lower_bound ??lower_bound可以二分找到数据序列中第一个大于等于x的数
??lower_bound默认队列中的数据是从小到大进行排序的，使用方法是lower_bound( begin, end, num)。假定对于a数组，例如从[1，len）区间里查找第一个大于等于x的数lower_bound(a+1, a+1+len, x)。从[0，len）区间里查找第一个大于等于x的数lower_bound(a, a+len, x)。假如查到该数，就返回这个数的地址，如果查不到，则返回队列的末尾end。那么我们如何确定他的下标呢，很简单，只需要减去数组的起始地址就能得到偏移量也就是他的下标了。比如:

int k = lower_bound(a, a+len, x) - a; //k就是在数组a中第一个大于等于x的元素的下标 ... = a[k];

??这里多插一句队列的末尾在哪，end在队列中最后一个元素的后边，如下表所示，8个元素的队列，end在第8个元素的后面：

1	2	3	4	5	6	7	8	end

对于下列这个具体的数据序列,长度len = 8，找第一个大于等于3的元素。

A序列的序号	0	1	2	3	4	5	6	7
值	2	3	3	3	3	4	4	5

k = lower_bound(A,A+len,3) - A； 此时k = 1，也就是该元素在序列中的位置。
??这是对于非下降序列来说的，可以找到第一个大于等于x的数，那么对于非上升序列呢，我们去找一个小于等于x的数，这样写就不对了，就需要更改lower_bound的默认比较器，从其默认的“”改成“”，这就需要我们手写一个比较器。

bool cmp(const int& a, const int& b){return a > b; } int k = lower_bound(a, a + n, x, cmp) - a;

或者我们可以使用STL自带的比较器，greater()提供了一个大于函数。

int k = lower_bound(a + 1, a + 1 + n, x, greater() ) - a;

upper_bound 【[LIS&LDS详解]导弹拦截——洛谷-P1020】upper_bound与lower_bound最大的不同，upper_bound找到的是第一个x的数。再拿上边的数组为例，长度len = 8，找第一个大于3的元素。

A序列的序号	0	1	2	3	4	5	6	7
值	2	3	3	3	3	4	4	5

k =upper_bound(A,A+len,3) - A； 此时k = 5。
从另一种方面来解释 ??对于lower_bound(array, array+len, x)，相当于找到的是在保持序列仍有序时，x所能插入到原序列的最前的位置。而对于upper_bound(array, array+len, x)是保持原序列有序时，所能插入到原序列的最后的位置。
以3为例,可插入到元素之前的位置

A序列的序号	0	1	2	3	4	5	6	7
值	2	3	3	3	3	4	4	5
可插入位置
		lower				upper

插入到上面带箭头的位置的元素之前，都可以保证插入后的元素有序。
最长上升子序列（LIS）最长下降子序列（LDS）思路 AC代码

#include #include #include using namespace std; #define maxn 1000100int d[maxn], f[maxn], t[maxn]; int main(){ int k = 0; while(scanf("%d", &d[k]) != EOF){ k++; }int len = 1; f[len] = d[0]; int len1 = 1; t[len1] = d[0]; for(int i = 1; i < k; i++){ if(d[i] <= f[len]){ len++; f[len] = d[i]; }else{ int b = upper_bound(f+1, f+len+1, d[i], greater()) - f; f[b] = d[i]; }if(d[i] > t[len1]){ len1++; t[len1] = d[i]; }else{ int b = lower_bound(t+1,t+len1+1,d[i])-t; t[b] = d[i]; } } cout << len << endl; cout << len1 << endl; return 0; }

非常简单的测试用代码

#include using namespace std; int main(){ int a[] = {2, 3, 3, 3, 3, 4, 5, 6}; int k1 = lower_bound(a, a+8, 3) - a; int k2 = upper_bound(a, a+8, 3) - a; cout << "lower_bound: " << k1 << endl; cout << "upper_bound: " << k2 << endl; }