https://www.luogu.com.cn/problem/P1020
O（nlogn）的总体思路：单调栈+贪心+二分替换值
字太多辣懒得打:(
引用Bianca_模拟的过程：
“
a 数组存所有的导弹 x数组存当前拦截的导弹的高度
len 记录当前最多能拦截多少导弹(实际是最长不升子序列即x数组的长度) 同时是最后的答案
下面是过程模拟环节：
样例：389 207 155 300 299 170 158 65
外层从 1 到 n 枚举 i 扫一遍序列
i = 1 时： x 数组为空 len = 0 所以直接将a [ i ]放进x数组 len + +
(x 数组：389)
i = 2 时： a [ i ] <= x [ len ] 也就是说这一发导弹不高于当前拦截的最后一发导弹的高度 符合条件 直接放进x数组 len + +
(x 数组：389 207)
i = 3 时： 同 i = 2情况
(x 数组：389 207 155)
i = 4 时：a [ i ] > x [ len ] 妈耶高于了 那就拦截不了了 我们考虑这个数还有什么用：假如用300代替207的话 不会破坏子序列的性质 而且后面拦截的导弹还有更大的选择空间 这个在后面就有所体现了
(x 数组：387 300 155)
i = 5 时：我们发现仍然是a [ i ] > x [ len ] 那我们再用299代替155
(x 数组：387 300 299)
i = 6~8 时：都满足a [ i ] <= x [ len ] 太好了 都可以继续拦截
(x 数组：387 300 299 170 158 65)
模拟完毕 在最后一步这种做法的优势( ? ? ? )就显示出来了 如果仍然是387 300 155这个序列的话 就只能再拦截最后一发导弹了 什么?你问我二分在哪？二分查找当然是用来找替换的位置的啦
”
“
不知道您会不会有这样的疑问：
如果只是389 207 155 300这个序列的话389 300 155这个顺序是无法拦截的呀(不符合导弹发送顺序)蒟蒻的我对此疑惑
后来想通：
这是不影响最长不升子序列的长度的(也就是389 300 155和389 207 155是一样的) 因为用300代替207只在由于这个改变而引起的后面的x数组更新时(389 207 155——>387 300 299时) 会起到扩大拦截导弹的选择空间的作用 没起到怎么办？ 那就假装没变不就完了(这就是389 300 155和389 207 155一样的原因)
”
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e5+100; typedef long long LL; LL a[maxn],d[maxn],k[maxn],n=1,cnt=0,ans=0; bool cmp(LL A,LL B){ return A>B; } int main(void) { cin.tie(0);std::ios::sync_with_stdio(false); while(cin>>a[n]) n++; n--; d[++cnt]=a[1];k[++ans]=a[1]; for(LL i=2;i<=n;i++){ if(d[cnt]>=a[i]) d[++cnt]=a[i]; else{ d[upper_bound(d+1,d+1+cnt,a[i],cmp)-d]=a[i]; } if(k[ans]<a[i]) k[++ans]=a[i]; else{ k[lower_bound(k+1,k+1+ans,a[i])-k]=a[i]; } } cout<<cnt<<endl<<ans<<endl; return 0; }双倍经验:
HDU - 5748
#include<iostream> #include<vector> #include<queue> #include<cstring> #include<cmath> #include<map> #include<set> #include<cstdio> #include<algorithm> #define debug(a) cout<<#a<<"="<<a<<endl; using namespace std; const int maxn=1e5+100; typedef long long LL; LL dp1[maxn],dp2[maxn],a[maxn]; LL n=1; int main(void) { ///cin.tie(0);std::ios::sync_with_stdio(false); while(cin>>a[n]) n++; n--; LL cnt1=1; LL ans=1; dp1[cnt1]=a[1]; for(LL i=2;i<=n;i++){ LL id=upper_bound(dp1+1,dp1+cnt1+1,a[i],greater<LL>())-dp1; ///debug(id); if(id>cnt1){ dp1[++cnt1]=a[i]; ans=max(ans,cnt1); } else{ dp1[id]=a[i]; } } /// for(LL i=1;i<=cnt1;i++) cout<<dp1[i]<<" "; /// cout<<endl; cout<<ans<<endl; cnt1=1; ans=1; dp2[cnt1]=a[1]; for(LL i=2;i<=n;i++){ LL id=lower_bound(dp2+1,dp2+cnt1+1,a[i])-dp2;///找严格大于的第一个数 ///debug(id); if(id>cnt1){ dp2[++cnt1]=a[i]; ans=max(ans,cnt1); } else{ dp2[id]=a[i]; } } cout<<ans<<endl; return 0; }
