https://www.luogu.org/problemnew/show/P1020

C++版本一

STL+二分+DP

題解：求一個序列里面最少有多少最長不上升序列等于求這個序列里最長上升序列的長度。我們用f[x]數組（第一問）來記錄當前長度為x的不上升序列中最大的結束點（這個運用了貪心的思想），如果當前數小于等于當前的最長不上升序列的結束點，那么我們把當前最長的不上升序列長度加一，把當前數作為這個 不下降序列的結束點，不然我們就用二分查找（為什么可以呢？這是因為我們運用了貪心的思/想后能保證長度越大的不上升序列結束點越小），試著用當前數去更新長度為x的不上升序列的結束點（又是貪心的思想，只更新長度最長且結束點小于自己的），然后第二問你再反著做就行了（把大于等于改為小于）

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; typedef __int128 lll; const int N=100000+100; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int a[N]; int f[N],l[100005]; struct cmp{bool operator()(int a,int b){return a>b;}}; int main() { #ifdef DEBUGfreopen("input.in.txt", "r", stdin);//freopen("output.out", "w", stdout); #endifwhile(scanf("%d",&a[++n])!=EOF);n--;int con=1,cont=1;l[1]=f[1]=a[1];for(int i=2;i<=n;i++){if(l[cont]>=a[i])l[++cont]=a[i];elsel[upper_bound(l+1,l+cont+1,a[i],cmp())-l]=a[i];if(f[con]<a[i])f[++con]=a[i];elsef[lower_bound(f+1,f+con+1,a[i])-f]=a[i];}cout<<cont<<" "<<con;//cout << "Hello world!" << endl;return 0; }

C++版本二

二分+DP

#include<cstdio> #include<string.h> #include<iostream> using namespace std; const int maxn=100005; int a[maxn]; int f[maxn]; int main() {int n=0;int l,r,mid;while(scanf("%d",&a[++n])!=EOF)continue;n--;f[0]=1234123412;//這個數要大于50000，不然可能你就無法更新int ans1=0;for(int i=1;i<=n;i++){if(f[ans1]>=a[i]){f[ans1+1]=a[i];//結束點為a[i]ans1++; //當前最長不上升序列的長度加一}else {//二分查找l=0;r=ans1;while(l<r){mid=(l+r)/2;if(f[mid]>=a[i])l=mid+1;else {r=mid; }}if(l!=0)f[l]=a[i];}}cout<<ans1<<endl;//輸出第一問的答案memset(f,-1,sizeof(f));//這次前面要盡量小了，不然又無法更新int ans2=0;for(int i=1;i<=n;i++){if(f[ans2]<a[i]){f[ans2+1]=a[i];//結束點為a[i]ans2++; //當前最長上升序列長度加一}else {//二分查找l=0;r=ans2;while(l<r){mid=(l+r)/2;if(f[mid]>=a[i])r=mid;else {l=mid+1; }}f[l]=a[i];}}cout<<ans2<<endl;//輸出第二個答案 }

C++版本三

樹狀數組?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int f[1000000]; int z[1000000]; int lowbit(int x) {return x&-x; } int big; inline int ask(int x)//這是用來求單調上升子序列的 {int r=0;for(int i=x;i>0;i-=lowbit(i))r=max(r,f[i]);return r; } inline void add(int x,int v)//這也是用來求單調上升子序列的 {for(int i=x;i<=big;i+=lowbit(i))f[i]=max(f[i],v); } inline int que(int x)//這是用來求最長單調不升子序列的 {int r=0;for(int i=x;i<=big;i+=lowbit(i))r=max(r,f[i]);return r; } inline void psh(int x,int v)//這也是用來求最長單調不升子序列的 {for(int i=x;i>0;i-=lowbit(i))f[i]=max(f[i],v); } int tot; int a[1000000]; int ans; int main() {tot=1;while(scanf("%d",&a[tot])!=EOF){big=max(big,a[tot]);z[tot]=a[tot];tot++;}tot--;//讀入并統計個數for(int i=1;i<=tot;i++)//求最長單升子序列，樹狀數組中保存的是0~a[i]的最大值{int x=ask(a[i])+1;ans=max(ans,x);add(a[i]+1,x);//因為是嚴格單升所以這里要+1}memset(f,0,sizeof(f));//清空樹狀數組，用來求下面的不降子序列int num=0;for(int i=1;i<=tot;i++)//求最長不降子序列，樹狀數組里存的是a[i]~inf的最大值{int x=que(a[i])+1;num=max(num,x);psh(a[i],x);//因為是不升而不是嚴格單降所以不用-1或+1}printf("%d\n%d",num,ans);return 0; }

C++版本四

#include<algorithm> #include<cstdio> #include<cstring> using namespace std; int n=0,a[100001],f[100001],d[100001],ans=1,t=0; int main() {while(~scanf("%d",&a[++n]));//讀入數據方法n--;//n是導彈數，由于某些原因要--for(int i=1; i<=n; i++) {f[i]=1;for(int j=t; j>0; j--)if(a[i]<=a[d[j]]) {f[i]=f[d[j]]+1;break;}t=max(t,f[i]);d[f[i]]=i;//簡單的維護過程ans=max(ans,f[i]);}printf("%d\n",ans);ans=1;t=0;for(int i=1; i<=n; i++) {f[i]=1;for(int j=t; j>0; j--)if(a[i]>a[d[j]]) {f[i]=f[d[j]]+1;break;}t=max(t,f[i]);d[f[i]]=i;ans=max(ans,f[i]);}printf("%d",ans); }

?

總結

以上是生活随笔為你收集整理的导弹拦截的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。