①题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行，若干个整数，中间由空格隔开。
输出格式
两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例
说明/提示
对于前50%数据，满足导弹的个数不超过10^4个。该部分数据总分共100分。可使用O(n2)做法通过。
对于后50%的数据，满足导弹的个数不超过10^5个。该部分数据总分也为 100 分。请使用O(nlogn)做法通过。
对于全部数据，满足导弹的高度为正整数，且不超过 5×(10^4)。
②题目分析和部份代码
由题可知，若我们要拦截下敌国的导弹，则需发射高度大于等于敌国发射的导弹。故求最多拦截多少导弹即求非递增子序列的最长长度，求最少配备多少拦截系统即求非递增子序列的最少条数。
（1）求非递增子序列的最长长度
如上图：
左图：若我们从头开始只找相邻连续非递增序列，此时最长长度为3；
右图：将各序列尽量合并，组成最长长度为4。
发现不能只比较相邻元素，所以我们需要遍历前面的序列，以便寻找到最佳长度。故每次将第i个的最好状态（即到第i个序列的最长长度）存入，等到判断第i+1时，若满足小于等于第i个元素，则直接在第i个最好状态上加1，此时即第i个元素基础上的最好状态，可此时是第i+1的最好状态吗？不确定，故继续向前遍历，直到找到第i+1的最好状态。
代码实现：
int main()
{
int num[100],max_len[100],max=0;
//假定num序列已输入，max_len为每个元素所在序列的最好状态,max为最长长度
max_len[1]=1;//第一个元素的最佳长度为1
for(int i=2;i<=n;i++)
{
max_len[i]=1;//1为该元素本身
for(int j=i-1;j>=1;j--)
{
if(num[i]<=num[j])
max_len[i]=max_len[j]+1>max_len[i]?max_len[j]+1:max_len[i];
//遍历前i-1个，寻找该元素所在序列最好状态
}
max=max_len[i]>max?max_len[i]:max;//更新最长长度
}
}优化代码：
从两层for循环知，该代码的时间复杂度为O(n^2)，只能通过50%的测试用例，故要对代码进行优化。
假设已知的序列长度中，最优长度时第i个元素刚好接入末尾，那么此时肯定是第i个元素的最好状态，即可以直接continue判断下一个元素，不需要再遍历取最好状态。
若无法接入最优长度，我们就判断是否能接入次优长度，一直取到长度为1都不能接入，则它只能自己重新构建一个序列。
如何判断是否能接入次优长度，我们知道次优长度时元素值大概率不唯一，那么如果此时取最大那个元素值，就会对后面即将接入的元素容纳度更高。例如：140、90、40和200、120两条序列，长度为2时最大的元素值取120，此时即将接入值为100，可接入；若是90则不可接入。故优化代码只需要增加一个数组存储每一个长度时可容纳的最大值。
int main()
{
int num[100],f[100],fmax=1;
//假定num序列已输入，f为每个长度可容纳的最大值（下标）,fmax为最长长度（初始为1）
f[1]=0;
for(int i=2;i<=n;i++)
{
if(num[i]<=num[f[fmax]]) //与最优长度的最大值比较
{
++fmax; //可容纳，最优长度更新
f[fmax]=i; //更新最新最优长度的可容纳度
}
else if(fmax==1) //边界处理，长度为1时都无法接入，即更新
{
f[fmax]=i;
}
else //最优长度无法接入
{
for(int j=fmax-1;j>=1;j--) //与次优长度及以下最大值比较
{
if(num[i]<=num[f[j]]) //找到可接入长度
{
if(num[i]>num[f[j+1]]) //判断接入完成后的长度是否需要更新可容纳度
{
f[j+1]=i; //与之前该长度的可容纳度比较，更新
}
break;
}
else if(j==1) //边界处理，长度为1时都无法接入，即更新
{
f[j]=i;
}
}
}
}
}（2）求非递增子序列的最少条数
例：389、207、155、300、299、170、158、65
同理，需要一个数组存储前i-1个的最少条数，若第i个与第i-1个发生冲突，无法接入序列，则取第i-1个基础上加1的条数，遍历前i-1最少条数，取遍历中最大的条数，即为第i个的最少条数。
代码实现：
int main()
{
int num[100],lian[100],min=0;
//假定num序列已输入，lian为每个元素所在序列的最少条数,min为最少条数
lian[1]=1;//第一个元素的最少条数为1
for(int i=2;i<=n;i++)
{
lian[i]=1;//1为最短
for(int j=i-1;j>=1;j--)
{
if(num[i]>num[j]) //与前i-1个元素发生冲突
lian[i]=lian[j]+1>lian[i]?lian[j]+1:lian[i];//更新最少条数
}
min=lian[i]>min?lian[i]:min;//更新
}
}代码优化：
同（1）理，想要优化代码，则必须减少不必要的比较。
我们可以知道，一个序列只有和最末端元素比较即可得知是否要增加新的序列，那么多个序列多个末端时要如何比较呢?还是讨论可容纳度，若末端可容纳度越高，则序列所需越少，所以我们一般先从末端最小的开始接入，一直消耗末端值小的序列，减少它们的可容纳度，这样就可以保证末端值大的序列的可容纳度高。即需要一个数组存储每个序列的末端值（每个序列最小值）。
int main()
{
int num[100],l[100],llen=1;
//假定num序列已输入，l为每个序列的末端值（下标）,llen为最少条数（初始为1）
l[1]=1; //第一条序列的末端值为第一个元素
for(int i=2;i<=n;i++)
{
if(num[i]>num[l[llen]]) //直接先判断是否需要增加新的条数，即取所有条数中最大的末端值
{
++llen;
l[llen]=i;
}
else //不需要增加新的条数，则更新某一序列的末端值
{
for(int j=1;j<=llen;j++)
{
if(num[i]<=num[l[j]]) //发现可接入在此序列末端，则更新
{
l[j]=i;
break;
}
}
}
}
}注意：因为条数从1开始存入，且每一次更新的条数末端值已经过从小到大判断和更新，所以不用担心数组中的末端值是否有序。
③完整代码
#include<stdio.h>
int num[100000],f[100001],l[100001];
int main()
{
int n=0,fmax=1,llen=1;
while(scanf("%d",&num[n])!=EOF)
{
++n;
}
f[1]=0;
for(int i=1;i<n;i++)
{
if(num[i]<=num[f[fmax]])
{
++fmax;
f[fmax]=i;
}
else if(fmax==1)
{
f[fmax]=i;
}
else
{
for(int j=fmax-1;j>=1;j--)
{
if(num[i]<=num[f[j]])
{
if(num[i]>num[f[j+1]])
{
f[j+1]=i;
}
break;
}
else if(j==1)
{
f[j]=i;
}
}
}
}
l[1]=0;
for(int i=1;i<n;i++)
{
if(num[i]>num[l[llen]])
{
++llen;
l[llen]=i;
}
else
{
for(int j=1;j<=llen;j++)
{
if(num[i]<=num[l[j]])
{
l[j]=i;
break;
}
}
}
}
printf("%d\n%d",fmax,llen);
return 0;
}④关于输入规则的小tips
scanf不读入"\n"，若是文件，则会出现EOF停止输入；若终端输入，则需要自己按住Ctrl+z+enter再回车才能停止输入。
标签：洛谷,int,max,条数,num,P1020,序列,长度,拦截 From： https://blog.csdn.net/weixin_73296216/article/details/137277655