刚学习的最长不递增子序列的新求法

P1020 [NOIP1999 提高组] 导弹拦截 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

在做这题的时候学到的

我看说是复杂度在O(nlogn)的算法才能通过这题

普通的办法就不行了（之前写过）

然后我去看题解，学了这种新的方法

网址如下：题解 P1020 【[NOIP1999 普及组] 导弹拦截】 - 古明地觉世界第一！ - 洛谷博客 (luogu.com.cn)

然后自己写了下面的这个代码：

#include<stdio.h>
#include<ctype.h>
void scanf_line(void);
int dic(int l, int u, int hi);
int dp[10], f[10], num[10];
int len, maxn = 1;

int main(void)
{
    //输入
    scanf_line();
    //求最长不递增子序列
    f[1] = num[1];
    for(int i = 2; i <= len; i++)
    {
        //二分法求fx最逼近hi时的x，更新dp以及f，maxn
        dp[i] = dic(1, maxn, num[i]) + 1;
        f[dp[i]] = num[i];
        maxn = (maxn > dp[i]) ? maxn : dp[i];
    }
    //输出
    printf("%d", maxn);

    return 0;
}
void scanf_line(void)
{
    int ext = 0;
    for(char c; (c = getchar()) != '\n'; )
        if(isdigit(c))
            ext = ext * 10 + c - '0';
        else
            num[++len] = ext, ext = 0;
    num[++len] = ext;
    return;
}
int dic(int l, int u, int hi)
{
    //初始时的意外情况
    if(f[l] <= hi)  return 0;
    if(f[u] >= hi)  return u;
    //正常结束的情况
    if(u - l <= 1)  return l;

    int mid = (l + u) / 2;
    if(f[mid] < hi)  return dic(l, mid, hi);
    else if(f[mid] > hi)  return dic(mid, u, hi);
    else  return mid;
}

这个代码只求了最大不递增子序列的数量

为的是做上面那道题做准备

而第二位看题解是有两个方法

最多的方法就是利用Dliworth定理做的

等做完再水一篇文吧

看题解用C++的STL做的非常简洁，最近在学C++，准备“升级”了，晚上又看了MCTS，感觉脑子要炸掉

白天去练习了科三，简单来说就是感觉要寄了

最近事有点多啊。。。