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