本文主要是介绍(Luogu) p1020导弹拦截，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
https://www.luogu.org/problemnew/show/P1020
dp的做法，复杂度是 O(n^2)，只能得100分，一个dp求的是最长下降子序列长度，一个dp求的是最少有多少个最长不上升序列，
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int f[maxn];
int dp[maxn];
int main(){int n=0;int num=0;while(cin>>f[++n]){continue;} n--;dp[1]=1;int res=0;for(int i=2;i<=n;++i){dp[i]=1;for(int j=i-1;j>=1;--j){if(f[j]>=f[i]) dp[i]=max(dp[i],dp[j]+1);}res=max(res,dp[i]);}cout<<res<<endl;memset(dp,0,sizeof(dp));num=0; for(int i=1;i<=n;i++){dp[i]=1; //初始化,dp[i]记录着要将第i个击落的最少系统（只考虑第i个 for(int j=1;j<i;j++)if(f[i]>f[j]&&dp[i]<dp[j]+1){ //第j个后面还有再布置一套新的要dp[j]+1个才能完成任务，如果//现在dp[i]已经大于等于这个数那就不需要更新了，dp[i]=max(dp[i],dp[j]+1) dp[i]=dp[j]+1;//必须再用新系统} num=max(num,dp[i]); //更新必须用的系统数}
// for(int i=1;i<=n;++i){
// cout<<dp[i]<<' ';
// }
// cout<<endl;cout<<num<<endl;return 0;
} 第二种方法是要用到dilworth定理，那就是，求一个序列里面最少有多少最长不上升序列等于求这个序列里最长上升序列的长度
用一个二分，复杂度就降到O(nlogn) （我也是看的洛谷题解的第一篇，想破脑袋也想不出来 dp+贪心
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int h[maxn];
int f[maxn];
int main(){int n=0,ans1=0,ans2=0;while(cin>>h[++n]){continue;} n--;f[0]=9e6+5;for(int i=1;i<=n;++i){//最长不下降序列长度 if(f[ans1]>=h[i]){f[++ans1]=h[i];//最长不上升序列的长度+1 }//f[x]代表长度为x的最大结点 else{int l=0,r=ans1;while(r>l){int mid=(l+r)/2;if(f[mid]>=h[i]){l=mid+1;}else r=mid;} if(l!=0) f[l]=h[i];}}cout<<ans1<<endl; memset(f,-1,sizeof(f)); for(int i=1;i<=n;++i){//最长上升序列长度 if(h[i]>f[ans2]){f[++ans2]=h[i];//最长上升序列的长度+1 }//f[x]长度为x的的最小节点 else{int l=0,r=ans2;while(r>l){int mid=(l+r)/2;if(h[i]<=f[mid]){r=mid;}else l=mid+1;} f[l]=h[i];}} cout<<ans2<<endl;return 0;
}
这篇关于(Luogu) p1020导弹拦截的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
