题目类型

最长上升子序列 + 贪心

给你一组数，一个仪器只能从大到小的遍历
最少需要几个仪器才能遍历所有的数。

笔记

求整个数列的最长上升子序列的长度 与 最少用多少个非上升子序列能够表示整个数列  可以用同一个方式解决。

因为：
求最少用多少个非上升子序列能够表示整个数列使用到了贪心的思路

每一个数h[i]分为两种情况：
1.将当前h[i]放入到当前存在的非上升子序列的末尾数值 >= h[i]  并且末尾数值与 h[i]差值最小的非上升子序列中。
2.如果不存在这么一个非上升子序列的末尾数值 >= h[i]，全部都 < h[i]的话就创建一个新的非上升子序列存入h[i]作为其当前末尾数值。

而这个思路的实现方式，多个非上升子序列用g[N]表示,

每次h[i]找到当前 序列中末尾最后一个数值 < h[i]的序列下标j，
并在j+1的序列g[j + 1]中用h[i]去更新这个序列的末尾值。

（而这个思路与最长上升子序列2的思路是一样的，所以这两个类型可以使用同一个解法求解）

题目

1010.拦截导弹

代码

# include <iostream>
using namespace std;
const int N = 1010;

int h[N];
int f[N];
int g[N];

int n;

int main()
{
    while(~scanf("%d",&h[n + 1]))
    {
        n++;
    }
    for(int i = n ; i >= 1 ; i--)
    {
        f[i] = 1;
        for(int j = n ; j > i ; j--)
        {
            if(h[j] <= h[i])
            {
                f[i] = max(f[i],f[j] + 1);
            }
        }
    }
    int res = 0;
    for(int i = 1 ; i <= n ; i++)
    {
        res = max(res,f[i]);
    }
    printf("%d\n",res);

    //下面的代码可以使用二分
    int cnt = 0;  // 当前的区间数
    for(int i = 1 ; i <= n ; i++)
    {
        int k = 0;
        while(k < cnt && h[i] > g[k])
        {
            k++;
        }
        g[k] = h[i];
        if(cnt == k)
        {
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;

    //从79行以后可以使用二分进行查找。找到第一个大于等于h[i]的值，然后将这个值改为小的值。但是要注意可能二分的数组中没有比h[i]要大的值，所以h[len] = 0x3f3f3f3f这样如果h[i]最大的话就会找到h[len]的位置，改变h[len]的值 = h[i]，然后len++.h[新len] = 0x3f3f3f3f;

    /*
    //使用二分找到大于当前h[i]的第一个数，如果没有的话，就在最后插入
        int len = 2;
        g[1] = h[1];
        g[len] = 0x3f3f3f3f;
        for(int i = 2 ; i <= n ; i++)
        {
            int l = 1;
            int r = len;
            while(l < r)
            {
                int mid = (l + r) / 2;
                if(g[mid] >= h[i])
                {
                    r = mid;
                }
                else
                {
                    l = mid + 1;
                }
            }
            if(l == len)
            {
                g[len++] = h[i];
                g[len] = 0x3f3f3f3f;
            }
            else
            {
                g[l] = h[i];
            }
        }
        printf("%d\n",len - 1);  //因为h[len]的值为0x3f3f3f3f.
    */


    //而这个思路是不是很熟悉，这个思路就是最长上升子序列II的贪心解法思路。二者实际上思路是一样的。

    /*
        求整个数列的最长上升子序列 与 最少用多少个非上升子序列能够表示整个数列  可以用同一个方式解决。
    */
}