题目1262：Sequence Construction puzzles(I)_构造全递增序列

本文主要是介绍题目1262：Sequence Construction puzzles(I)_构造全递增序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：

给定一个整数序列，请问如何去掉最少的元素使得原序列变成一个全递增的序列。

输入：

输入的第一行包括一个整数N(1<=N<=10000)。
接下来的一行是N个满足题目描述条件的整数。

输出：

可能有多组测试数据，对于每组数据，
输出去掉最少的元素后的全递增序列。

样例输入：

8
186 186 150 200 160 130 197 220

样例输出：

150 160 197 220

提示：

如果有多个结果序列满足条件，输出相对位置靠前的那个序列。

C++代码：

#include<iostream>
#include<stack>
using namespace std;
int arr[10010];
int dp[10010];
int path[10010];
stack<int> S;
int main(){//freopen("1.txt","r",stdin);int n;while(cin>>n){while(S.empty()==false)S.pop();for(int i=0;i<n;i++)cin>>arr[i];for(int i=0;i<n;i++){path[i]=-1;dp[i]=1;}dp[0]=1;path[0]=-1;for(int i=1;i<n;i++){int curc=1,tmpindex=-1;for(int j=0;j<i;j++){if(arr[i]>arr[j]&&dp[j]>=curc){tmpindex=j;curc=dp[j]+1;}}dp[i]=curc;path[i]=tmpindex;}int index=0,max=0;for(int i=0;i<n;i++){if(dp[i]>max){max=dp[i];index=i;}}while(index!=-1){S.push(index);index=path[index];}bool first=true;while(S.empty()==false){int t=S.top();S.pop();if(first){cout<<arr[t];first=false;}else{cout<<" "<<arr[t];}}cout<<endl;}return 0;
}

这篇关于题目1262：Sequence Construction puzzles(I)_构造全递增序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---