UVa 11456 – Trainsorting

程序员朝麟技术 2022年11月6日

0 收藏 342 点赞 348 浏览 796 个字

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

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

 #include <cstdio>
 #include <algorithm>
 using namespace std;
 #define MAXN 2010 int a[MAXN], lis[MAXN], lds[MAXN]; int main()
 {
 #ifdef LOCAL
     freopen("in", "r", stdin);
 #endif
     int T;
     scanf("%d", &T);
     while (T--)
     {
         int n;
         scanf("%d", &n);
         for (int i = ; i < n; i++)
             scanf("%d", &a[i]);
         for (int i  = n-; i >= ; i--)
         {
             lis[i] = lds[i] = ;
             for (int j = i+; j < n; j++)
             {
                 if (a[i] < a[j])  lis[i] = max(lis[i], lis[j]+);
                 if (a[i] > a[j])  lds[i] = max(lds[i], lds[j]+);
             }
         }
         int ans = ;
         for (int i = ; i < n; i++)
             ans = max(ans, lis[i]+lds[i]-);
         printf("%d\n", ans);
     }
     return ;
 }