Trainsorting （最长上升(下降)子序列）

Trainsorting （最长上升(下降)子序列）

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers toput the cars in decreasing order of weight, with the heaviest car at the front of the train.Unfortunately, sorting train cars is not easy. One cannot simply pick up a car and place it somewhereelse. It is impractical to insert a car within an existing train. A car may only be added to the beginningand end of the train.Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add itto the beginning or end of her train, or refuse to add it at all. The resulting train should be as long aspossible, but the cars within it must be ordered by weight.Given the weights of the cars in the order in which they arrive, what is the longest train that Erincan make?InputThe first line is the number of test cases to follow. The test cases follow, one after another; the formatof each test case is the following:The first line contains an integer 0 ≤ n ≤ 2000, the number of cars. Each of the following n linescontains a non-negative integer giving the weight of a car. No two cars have the same weight.OutputOutput a single integer giving the number of cars in the longest train that can be made with the givenrestrictions.Sample Input13123Sample Output3

题目大概：

给你一个数t，t组样例，然后给你n个数，你可以按顺序，从这数中，去取数，加到自己手中，自己手中的数，是排成了一个自上而下的堆，上面小，下面大，取得的数，只能放在最下方，或者最上方。问最多，这个堆有多大。

思路：

可以先求出，以每个数结尾的最长上升子序列和最长下降子序列。

然后枚举每两个数（一个上升结尾，一个下降结尾），是否是最长的。

代码：

#include using namespace std;const int maxn=2010;int dp1[maxn];int dp2[maxn];int a[maxn];int main(){ int n,t; scanf("%d",&t); while(t--) { scanf("%d",&n); memset(dp1,0,sizeof(dp1)); memset(dp2,0,sizeof(dp2)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++)dp1[i]=1; for(int i=1;i<=n;i++)dp2[i]=1; for(int i=n;i>=1;i--) { for(int j=n;j>i;j--) { if(a[j]>a[i]) { if(dp1[i]a[j]) sum=max(sum,dp1[i]+dp2[j]); } } printf("%d\n",sum); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。