2014
03-06

# Trainsorting

Erin is an engineer. She drives trains. She also arranges the cars within each train. She prefers to put 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 somewhere else. It is impractical to insert a car within an existing train. A car may only be added to the beginning and end of the train.

Cars arrive at the train station in a predetermined order. When each car arrives, Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, 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 Erin can make?

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

The first line contains an integer 0 <= n <= 2000, the number of cars. Each of the following n lines contains a non-negative integer giving the weight of a car. No two cars have the same weight.

3
1
2
3

3

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <cstdlib>

using namespace std;
const int MAX=2005,INF=1<<30;
int a[MAX],c[MAX],
n,len;
int bsearchLDS(const int &v){
int l=1,r=len+1,m;
while(l<r){
m=l+(r-l)/2;
if(c[m]>v) l=m+1;
else r=m;
}
return l;
}
int bsearchLIS(const int &v){
int l=1,r=len+1,m;
while(l<r){
m=l+(r-l)/2;
if(c[m]<v) l=m+1;
else r=m;
}
return l;
}
int LDS(const int &i){
int pos;
len=1;
c[len]=a[i];
for(int j=i+1;j<n;j++){
pos=bsearchLDS(a[j]);
if(pos==1)
continue;
c[pos]=a[j];
if(pos>len)
len=pos;
}
return len;
}
int LIS(const int &i){
int pos;
len=1;
c[len]=a[i];
for(int j=i+1;j<n;j++){
pos=bsearchLIS(a[j]);
if(pos==1)
continue;
c[pos]=a[j];
if(pos>len)
len=pos;
}
return len;
}
int main()
{
// freopen("i.txt","r",stdin);
int nCase,t1,t2,l,maxVal;
// cin>>nCase;
while(cin>>n){
maxVal=0;
//memset(a,0,sizeof(a));
//memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++){
//LDS;
t1=LDS(i);
t2=LIS(i);
// cout<<i<<' '<<a[i]<<endl;
// cout<<t1<<' '<<t2<<endl<<endl;
l=t1+t2-1;
if(l>maxVal)
maxVal=l;
//break;
}
cout<<maxVal<<endl;
}
return 0;
}

1. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？

2. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.