UVa 11456

　　题目大意：给一个车辆到达车站的序列（按时间先后），可以对车辆进行以下处理：插在队首、插在队尾或者拒绝进站。车站内的车辆必须按照重量大小从大到小排列，问车站内最多能有多少辆车辆？

　　假设车i是第一个进站，那么在i后面的车辆如果比i车重，可以插在i的前面，如果比i车轻，可以插在i的后面。这就变成了求以i为起点的最大递增子序列和最大递减子序列了，i首先进站的最大长度为LIS(i)+LDS(i)-1，找出其中的最大值就可以了。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MAXN 2010
 5 
 6 int a[MAXN], lis[MAXN], lds[MAXN];
 7 
 8 int main()
 9 {
10 #ifdef LOCAL
11     freopen("in", "r", stdin);
12 #endif
13     int T;
14     scanf("%d", &T);
15     while (T--)
16     {
17         int n;
18         scanf("%d", &n);
19         for (int i = 0; i < n; i++)
20             scanf("%d", &a[i]);
21         for (int i  = n-1; i >= 0; i--)
22         {
23             lis[i] = lds[i] = 1;
24             for (int j = i+1; j < n; j++)
25             {
26                 if (a[i] < a[j])  lis[i] = max(lis[i], lis[j]+1);
27                 if (a[i] > a[j])  lds[i] = max(lds[i], lds[j]+1);
28             }
29         }
30         int ans = 0;
31         for (int i = 0; i < n; i++)
32             ans = max(ans, lis[i]+lds[i]-1);
33         printf("%d
", ans);
34     }
35     return 0;
36 }

View Code

　　做的有点随便了，大概想了一下就开始写了，最初LIS(i)和LDS(i)保存的是以i为终点的最大XX子序列，根本就没想清楚，完全凭感觉了...后来改了还是WA了，然后就觉得是n可以等于0的问题，没好好看题-_-|| ，这个WA了4次才过，无语啊...