導彈攔截

鏈接

分析：經典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 }

View Code

轉載于:https://www.cnblogs.com/wolf940509/p/7008497.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/370292.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/370292.shtml
英文地址，請注明出處：http://en.pswp.cn/news/370292.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！