刚学习的最长不递增子序列的新求法-Toy模板网

这篇具有很好参考价值的文章主要介绍了刚学习的最长不递增子序列的新求法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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，感觉脑子要炸掉

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

最近事有点多啊。。。文章来源地址https://www.toymoban.com/news/detail-815668.html

到了这里，关于刚学习的最长不递增子序列的新求法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！