#include<bits/stdc++.h> using namespace std; int n=1, a[1000000], dp[1000000], b[2000000],c[2000000]; int main(){ while(cin>>a[n++]){ // cout<<n<<endl; for(int i=1;i<=n;i++){ c[i]=a[n-i+1]; } int b1=0; for(int i=1;i<=n;i++){ int x=upper_bound(b+1,b+1+b1,c[i])-b; if(x>=1&&x<=b1){ b[x]=c[i]; } else{ b1++; b[b1]=c[i]; } } cout<<b1<<endl; b1=0; for(int i=1;i<=n;i++){ int x=lower_bound(b+1,b+1+b1,a[i])-b; if(x>=1&&x<=b1){ b[x]=a[i]; } else{ b1++; b[b1]=a[i]; } } cout<<b1; return 0; }

LIS模型解决最多可以拦截多少颗炮弹+贪心 需要配置多少个系统，代码如下：

读入就是用变量记一下数组当前长度，只要输入 a[++n]!=EOFa[++n]!=EOFa[++n]!=EOF ,就一直读下去。 很明显，第一个问题是让求最长不升子序列，首先我们开两个 dp 数组，第一个 dp 数组求第一问，第二个求第二问，再开两个变量分别统计答案。我们先把第一项复制成 a 数组的第 1 项，无论如何至少你能打下来一个，所以 len1len_1len1 = 1，接下来我们从第二个数组元素循环，只要小要小于 dp 数组的前一项就 len1len_1len1 +1+1+1 并且 dplen1dp_len1dpl en1 =aia_iai 可是我们如果发现了当前元素比 dpdpdp 数组末位元素大，说明这个高度会更有潜力，因为这个高度较大，我们可以多打中几枚，我们就找到比它小（注：在 upperupperupper _ boundboundbound 里面 用 greater<typename>greater<typename>greater<typename> () ）的一个元素把它替换掉，这样就以 nlognnlognnlogn 的复杂 度解决了第一个问题。 第二个问题我们试着来考虑一下，发现第二个 dpdpdp 数组的第一项也可以用 aaa 数组的第一项先管着，同样 lenlenlen _ 222 =1=1=1 ，因为你至少要用一个系统。我们在从第二个元素扫的时候只要有一个高度比当前 dpdpdp 数组最后一个系统的高度大，你就直接再加 一个系统，因为前一个系统拦截不到这里。如果不是这样我们就考虑用之前用过的一个拦截系统把这个导弹给拦截下来，这意味着这个高度同样可以使我们拦截掉更多的导弹，我们就找一个高度刚好大于或者等于它的 dpdpdp 数组中的一个元素给替换成当前拦截的导弹高度值。说到这里，各位不难想到这其实就是求得最长上升子序列，同样以 nlognnlognnlogn 的时间复杂度求出了。

根据题目描述：导弹依次飞来，拦截时每一发炮弹都不能高于前一发的高度。那么最多能拦截的导弹数，其实就是最长的下降（非严格下降）子序列的长度。 第二问求最少要配备多少套这种导弹拦截系统？可以使用贪心思想，流程如下： 从前向后遍历每一个导弹高度，对于每一个数来说，有两种情况： 1. 所有拦截系统的最低高度都小于当前导弹高度，需要增加一套系统 2. 找到第一套系统，其拦截的最低高度大于等于当前导弹的高度，更新该系统的最低拦截高度。 AC代码

下降子序列+贪心

经典题型

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define maxn 1000010 using namespace std; typedef long long ll; ll a[maxn],n=1,dp1[maxn],dp2[maxn],len1,len2; inline void write(ll x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } int main(){ while(cin>>a[n]){ n++; } n--,len1=1,len2=1; dp1[1]=a[1],dp2[1]=a[1]; for(ll i=2;i<=n;i++){ if(a[i]<=dp1[len1]){ dp1[++len1]=a[i]; } else{ ll k1=upper_bound(dp1+1,dp1+len1+1,a[i],greater<ll>())-dp1; dp1[k1]=a[i]; } if(a[i]>dp2[len2]){ dp2[++len2]=a[i]; } else{ ll k2=lower_bound(dp2+1,dp2+len2+1,a[i])-dp2; dp2[k2]=a[i]; } } write(len1); puts(""); write(len2); return 0; }

点赞！！！

点赞！！！