本文主要是介绍刚学习的最长不递增子序列的新求法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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，maxndp[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';elsenum[++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，感觉脑子要炸掉
白天去练习了科三，简单来说就是感觉要寄了
最近事有点多啊。。。
这篇关于刚学习的最长不递增子序列的新求法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
