首页 > 代码库 > 导弹拦截
导弹拦截
链接
分析:经典DP题,最长不下降子序列的变种,同时需要记录路径,用pre[]数组记录当前结点的前一个结点的方法很妙
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "string" 5 #include "vector" 6 using namespace std; 7 const int maxn=110; 8 int dp[maxn]; 9 int pre[maxn]; 10 int main() 11 { 12 int x,n; 13 vector<int>h; 14 while(scanf("%d",&x)!=EOF){ 15 h.push_back(x); 16 } 17 int ans=0,cnt=0; 18 while(!h.empty()){ 19 n=h.size(); 20 for(int i=0;i<=n;i++) pre[i]=i; 21 for(int i=0;i<n;i++){ 22 dp[i]=1; 23 for(int j=0;j<i;j++){ 24 if(h[j]>h[i]&&dp[i]<dp[j]+1){ 25 dp[i]=dp[j]+1; 26 pre[i]=j; 27 } 28 } 29 } 30 int tt=0,pos; 31 for(int i=0;i<n;i++){ 32 if(dp[i]>tt){ 33 tt=dp[i]; 34 pos=i; 35 } 36 } 37 ans=max(tt,ans); 38 int flag=0; 39 while(!flag){ 40 h.erase(h.begin()+pos); 41 if(pos==pre[pos]) flag=1; 42 pos=pre[pos]; 43 } 44 ++cnt; 45 } 46 cout<<ans<<endl; 47 cout<<cnt<<endl; 48 }
导弹拦截
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。