003：士兵站队

Messj

[POJ 1836] 士兵站队 (Alignment)

题目描述

在军队中，一个团是由士兵组成的。在早晨的检阅中，士兵们在长官面前站成一行。但长官对士兵们的队列并不满意。士兵们的确按照他们的编号由小到大站成一列，但并不是按高度顺序来站的。于是，长官让一些士兵出列，其他留在队里的士兵没有交换位置，变成了更短的一列。这个队列满足一下条件：队伍里的每一个士兵都至少可以看见整个队伍的最前方或最后方,(如果一个士兵要看到队伍的最前方或最后方，那么在他的前方或后方，都没有比他高的人)。

现在按顺序给出一个队列里的每个士兵的身高，计算出若要形成满足上述条件的队列，长官至少需要让多少士兵出列。

输入

输入数据的第一行，包含一个整数n，表示原队列里士兵的数量。第二行，包含n个浮点数(最多有五位小数)，第i个浮点数表示队列中编号为i的士兵的身高hi。

其中：2 <= n <= 1000 ，且身高hi的取值范围[0.5,2.5]。

输出

包含一个整数，表示需要出列的最少士兵数。

样例输入       
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
样例输出
4


解析

这道题嘛，就是让队列里最少的士兵出列，使队列变成这么一个样子，如图-1。由于要求最少出列人数，也就是保留最多人数，于是这道题就有了求最长上升子序列的DP做法。对第i个人，计算1~i的最长上升序列(长度为l)与i+1~n的最长下降序列(长度为d)，对所有的i，取l+d的最大值max。答案即为n-max。二分+枚举也可求解。


DP解法：

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. const int maxn=1001;
   
5. int n;
   
6. double num[maxn];
   
7. int up[maxn],down[maxn];
   
8. 
   
9. int main()
   
10. {
    
11.         scanf("%d",&n);
    
12.         for(int i=0;i<n;i++)
    
13.         {
    
14.                 scanf("%lf",&num[i]);
    
15.                 up[i]=1;down[i]=1;
    
16.         }
    
17.         int ans=0;       
    
18.         for(int i=0;i<n;i++)
    
19.         {
    
20.                 for(int j=0;j<i;j++)
    
21.                 {
    
22.                         if(num[i]>num[j])
    
23.                         {
    
24.                                 if(up[i]<(up[j]+1))
    
25.                                         up[i]=up[j]+1;
    
26.                         }
    
27.                 }
    
28.         }
    
29.        
    
30.         for(int i=n-1;i>=0;i--)
    
31.         {
    
32.                 for(int j=n-1;j>i;j--)
    
33.                 {
    
34.                         if(num[i]>num[j])
    
35.                         {
    
36.                                 if(down[i]<(down[j]+1))
    
37.                                         down[i]=down[j]+1;
    
38.                         }
    
39.                 }
    
40.         }
    
41.        
    
42.         for(int i=0;i<n-1;i++)
    
43.         {
    
44.                 for(int j=i+1;j<n;j++)
    
45.                         ans=max(ans,up[i]+down[j]);
    
46.         }
    
47.         printf("%d\n",n-ans);
    
48. }

复制代码

二分+枚举

1. #include <cstdio>  
   
2. #include <algorithm>  
   
3. using namespace std;  
   
4. int const MAX = 1e3 + 5;  
   
5. int const INF = 0x3fffffff;  
   
6. int l[MAX], r[MAX];  
   
7. double lstk[MAX], rstk[MAX];  
   
8. double h[MAX];  
   
9.   
   
10. int main()  
    
11. {  
    
12.     int n, ltop = 0, rtop = 0;  
    
13.     scanf("%d", &n);  
    
14.     for(int i = 1; i <= n; i++)  
    
15.     {  
    
16.         scanf("%lf", &h[i]);  
    
17.         if(h[i] > lstk[ltop])  
    
18.             lstk[++ ltop] = h[i];  
    
19.         else  
    
20.         {  
    
21.             int low = 1, high = ltop, mid;  
    
22.             while(low <= high)  
    
23.             {  
    
24.                 mid = (low + high) >> 1;  
    
25.                 if(h[i] > lstk[mid])  
    
26.                     low = mid + 1;  
    
27.                 else  
    
28.                     high = mid - 1;  
    
29.             }  
    
30.             lstk[low] = h[i];  
    
31.       
    
32.         }  
    
33.        l[i] = ltop;  
    
34.     }  
    
35.     for(int i = n; i >= 1; i--)  
    
36.     {  
    
37.         if(h[i] > rstk[rtop])  
    
38.             rstk[++ rtop] = h[i];  
    
39.         else  
    
40.         {  
    
41.             int low = 1, high = rtop, mid;  
    
42.             while(low <= high)  
    
43.             {  
    
44.                 mid = (low + high) >> 1;  
    
45.                 if(h[i] > rstk[mid])  
    
46.                     low = mid + 1;  
    
47.                 else  
    
48.                     high = mid - 1;  
    
49.             }  
    
50.             rstk[low] = h[i];  
    
51.         }  
    
52.         r[i] = rtop;     
    
53.     }  
    
54.     int in = 0;  
    
55.     for(int i = 1; i < n; i++)  
    
56.         for(int j = i + 1; j <= n; j++)  
    
57.             in = max(in, (l[i] + r[j]));  
    
58.     printf("%d\n", n - in);  
    
59. }  

复制代码