题意：求出一个最长单调不增子序列和最少的个数的单调不加的子序列的个数。根据dilworth:最少的全集个数等于最大的反链的元素个数。可以将求最少的个数的单调不加的子序列的个数转化为求最长上升子序列的长度。于是用二分+贪心来写点击查看代码#include<iostream>#include

P1020[NOIP1999提高组]导弹拦截参考材料需要抽象一下，第一问就可以抽象为最长不上升子序列，第二问可以抽象为最长上升子序列长度。就如下图的情况：然后可以先\(n^2\)做法做，因为\(n\ge100000\)所以要滚动数组，求最长不上升子序列可以反向从n开始递推。我是n^2我不好

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;intn;inta[N];intq[N];signedmain(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); intx; while(cin>>x)a[++n]=x; intlen

前置：二分查找，最长单调不升子序列，最长单调不降子序列（dilworth）。题解：可以用来练习手写二分，二分优化的最长上升子序列时间复杂度O(nlogn)。但是坑是非常多的。代码：#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+10;inta[N],n,

传送门：P1020[NOIP1999提高组]导弹拦截题目大意：一个拦截导弹的系统，每次只能拦截高度不超过上一个的导弹求出：一个系统最多能拦截的导弹数量；要拦截所有导弹最少需要的该系统的数量。思路：第一问：一眼就是最长单调不上升子序列，朴素DP求解，复杂度为O(n^2)；请参考，能过掉50%

题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所

题目链接：导弹拦截思路    代码#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;inta[N],x,l,dp[N],maxn;intg[N],cnt;intmain(){while(cin>>x)a[++l]=x;for(inti=1;i<=l;i++){intk=1

原题链接：P1020[NOIP1999提高组]导弹拦截-洛谷|计算机科学教育新生态(luogu.com.cn)相当好的一道题，用于理解使用[[狄尔沃斯定理（Dilworth定理）]]当然这个定理肯定不止这么简单。第一问就是让求一个最大不上升子序列，如果用DP求解，将是\(O(n^2)\)的时间复杂度，而这道题

原题链接：https://www.luogu.com.cn/problem/P1020题意解读：拦截系统发射导弹的高度依次不增，计算能拦截的最大导弹数以及需要几套拦截系统。解题思路：问题1：最多能拦截多少导弹？由于发射导弹高度不增，所以求一个最长不增子序列即可得到最大拦截数。方法一、O(n^2)做法：动态规划。采

①题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截

链接：https://www.luogu.com.cn/problem/P1020这个题目一分为二：首先就是LIS：改下，改成最长不升子序列，复杂度：nlogn;然后用vector的贪心，复杂度：n^2(这里似乎可以二分降到nlogn，不过反正过了OwO!)被这个输入卡的好难受，建议用getline读取不确定的数题目：代码：#include<iostream>#incl

P1020[NOIP1999普及组]导弹拦截思考这题很显然是一道DP题，第一问就是求该序列的最长不下降子序列.先说最长不下降子序列的\(O(n^2)\)的做法.用\(dp_k\)表示第\(k\)

[NOIP1999普及组]导弹拦截题目描述某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以

题目大意：有一个数列，我们要获取一组子串，这个子串必须单调不增。问：（1）最长我们可以获取多长的这种子串（2）这个数列中最多有多少种这种子串解题思路：其中问题一是很典型的DP问题，最