一、lower_bound与upper_bound

#####1.作用

这两个是STL中的函数，作用很相似：
假设我们查找x，那么：
lower_bound(a +1, a +1+ n, x);
会找出序列中第一个**大于等于**x的数
upper_bound(a +1, a +1+ n, x);
会找出序列中第一个**大于**x的数
没错这俩就差个**等于**号╮(╯▽╰)╭

2.用法

以下都以lower_bound做栗子 (upper_bound同义)
它们俩使用的前提是一样的：序列是**有序**的
对于一个数组a，在[1,n]的区间内查找**大于等于**x的数(假设那个数是y)，函数就写成：
lower_bound(a+1,a+n+1,x)
函数返回一个指向y的指针
看着是不是很熟悉？回想sort使用的时候：
sort(a+1,a+1+n)
这里(a+1,a+1+n)的写法是不是很像？
STL里面的函数写区间一般都这个尿性
同样的，lower_bound和upper_bound也是可以加**比较函数**cmp的：cmp()
它们的实现方式是二分查找\(O(nlogn)\)

3.返回值

对于返回值我们有两种处理方式：

第一种：

许多人讨厌指针，那么我们用这个指针**减去**数组开头的指针(即**数组名**)，得到两个指针的差，就是**数组下标**，即：
int p=lower_bound(a_first, a_last, x, cmp)-a的首地址
那么a[p]就是要找的y (如果不知道为什么就记着好了)

第二种**(快速方法)**：

int *p=lower_bound(a_first, a_last, x, cmp)
那么*p就是要找的y

可以看出指针多么直接，不像数组下标还要倒腾一遍

总结一下：####

对一个**下降**序列a

int p = lower_bound(a +1, a +1+ n, x, greater<int>() ) - a;

a[p]即a[1]到a[n]中第一个小于等于x的数

二、一个序列中的最长上升子序列（LIS）

例：由6个数，分别是：**1 7 6 2 3 4**，求最长上升子序列。

评析：
首先，我们要理解什么叫做最长上升子序列：

1、最长上升子序列的元素不一定相邻
2、最长上升子序列一定是原序列的子集。

所以这个例子中的LISLIS就是：1 2 3 4，共4个

####1、\(O(n^2)\) 做法
首先我们要知道，对于每一个元素来说，最长上升子序列就是其本身。那我们便可以维护一个dp数组，使得**dp[i], dp[i]表示以第i元素为结尾的最长上升子序列长度**，那么对于每一个dp[i]而言，初始值即为1；
那么dp数组怎么求呢？我们可以对于每一个i，枚举在i之前的每一个元素j，然后对于每一个dp[j],如果元素i大于元素j，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值，取max.

for(int i=1;i<=n;i++)
{
dp[i]=1;//初始化
for(int j=1;j<i;j++)//枚举i之前的每一个j
if(data[j]<data[i] && dp[i]<dp[j]+1)
dp[i]=dp[j]+1;
//用if判断是否可以拼凑成上升子序列，
//并且判断当前状态是否优于之前枚举
//过的所有状态,如果是，则↓
//更新最优状态
}

最后，因为我们对于dp数组的定义是到i为止的最长上升子序列长度，所以我们最后对于整个序列，只需要输出dp[n](n为元素个数)即可。

从这个题我们也不难看出，状态转移方程可以如此定义：
#####下一状态最优值=最优比较函数（已经记录的最优值，可以由先前状态得出的最优值）
#####——即动态规划具有 *判断性继承思想*

2、\(O(nlogn)\)做法

我们其实不难看出，对于\(O(n^2)\)做法而言，其实就是暴力枚举：将每个状态都分别比较一遍。但其实有些没有必要的状态的枚举，导致浪费许多时间，当元素个数到了\(10^4-10^5\)以上时，就已经超时了。而此时，我们可以通过另一种动态规划的方式来降低时间复杂度：

将原来的dp数组的存储由数值换成**该序列中，上升子序列长度为i的上升子序列的最小末尾数值**

int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        f[i]=0x7fffffff;
        //初始值要设为INF
    }
    f[1]=a[1];
    int len=1;//通过记录f数组的有效位数，求得个数  
    for(int i=2;i<=n;i++)
    {
        int l=0,r=len,mid;
        if(a[i]>f[len])f[++len]=a[i];
        //如果刚好大于末尾，暂时向后顺次填充 
        else 
        {
        while(l<r)
        {   
            mid=(l+r)/2;
            if(f[mid]>a[i])r=mid;
    /*如果仍然小于之前所记录的最小末尾，那么不断
    向前寻找(因为是最长上升子序列，所以f数组必
    然满足单调) */
            else l=mid+1; 
        }
        f[l]=min(a[i],f[l]);//更新最小末尾 
        }
    }
    cout<<len;
}

####3、样例分析

下面只讨论2、3两问，第一问请读者自行根据代码理解。

对于本题给的样例来说，分别是： 

1 2 3 4 4 6 8

然后问 *“一套武器最多能摧毁多少水滴，如果要摧毁所有水滴最少需要配备多少套种这样的武器”*

评析：

首先，这道题给出条件*“以后每一个水滴都要大于前一个的重量”，*则要求一个最大上升的子序列，使用upper_bound()函数使复杂度降到\(O(nlogn)\)，对于第三问，运用

Dilworth定理：偏序集的最少反链划分数等于最长链的长度

那么所求武器所需最少数便是等价于其反链的最大长度——即一个最大不上升子序列，使用lower_bound()函数进行求解即可。
下面贴出\(O(nlogn)\)的完整代码

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<vector>
#include<fstream> 
using namespace std;
int num[100001],dp1[100001],dp2[100001];

bool cmp(const int &a, const int &b){
    return a>b;
}
int main(){
    int i=0,len=0;
    ///ifstream in("1204_1.in");
    //if (! in.is_open()){ cout << "Error   opening file"; exit (1); }
    /*
    while(!in.eof()){
        in>>num[++len];
    }*/
    
    while(cin>>num[++len]){
        
        char a=getchar();
        if(a!=' ') break;
    }
    cout<<len<<endl; 
    //cout<<num[2];
    //len--;
    //cout<<len;
    dp1[1]=num[1],dp2[1]=num[1];
    /*
    lower_bound  >=
    upper_bound  >
    */
    int pos=1,pos1=1;
    for(i=2;i<=len;i++){
        /*大于==最长上升子序列*/ 
        if(dp1[pos]<num[i]) dp1[++pos]=num[i];
        else{
            int p1=lower_bound(dp1+1,dp1+pos+1,num[i])-dp1;
            //返回第一个比num[i]大的数的下标，进行代替 
            dp1[p1]=num[i];
        }
        /*最少配备系统==最长不下降子序列*/ 
        if(dp2[pos1]>= num[i]) dp2[++pos1]=num[i];
        else{
            int p2=upper_bound(dp2+1,dp2+pos1+1,num[i],cmp)-dp2;
            //返回第一个小于等于num[i]的数的下标 
            dp2[p2]=num[i];
        }
    }
    cout<<pos<<endl<<pos1;

    return 0;
}