原题描述：
Alignment
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 1188 Accepted: 239
Description
In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight line in front of the captain. The captain is not satisfied with the way his soldiers are aligned; it is true that the soldiers are aligned in order by their code number: 1 , 2 , 3 , . . . , n , but they are not aligned by their height. The captain asks some soldiers to get out of the line, as the soldiers that remain in the line, without changing their places, but getting closer, to form a new line, where each soldier can see by looking lengthwise the line at least one of the line’s extremity (left or right). A soldier see an extremity if there isn’t any soldiers with a higher or equal height than his height between him and that extremity.
Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.
Input
On the first line of the input is written the number of the soldiers n. On the second line is written a series of n floating numbers with at most 5 digits precision and separated by a space character. The k-th number from this line represents the height of the soldier who has the code k (1 <= k <= n).
There are some restrictions:
• 2 <= n <= 1000
• the height are floating numbers from the interval [0.5, 2.5]
Output
The only line of output will contain the number of the soldiers who have to get out of the line.
Sample Input
8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2
Sample Output
4
题目大意：
给出系列数字，要求求出一个最长串，使得任意一个数字都不在两个大于等于它的数字中间
题意理解
这题主要是要求一个不降序列和一个不升序列的序列，由此，可以看到跟2533（最长不降序列）很相像。实际上，也只要考虑几个小问题就行了。
解题思路：
在2533（最长不降序列）中，我们只要用一个1000的数组就行了。其状态转移方程为
F(K) = MAX(F(A1),F(A2)..F(Ai)) + 1,其中0=<A1=<A2..<Ai=<N,Seq[k] >= F(Ai)。即第K个数字及其之前数字的最长不降序列为其之前的某个小于它的数字的最长不降序列加一。
对于这题，则可用一个二维数组。其第一维与2533相同，储存其最长不降序列；第二维则储存最长不升序列。具体为：
F(K,0)=MAX(F(A1,0)…F(Ai,0)) + 1; F(K,1) = MAX(F(B1,0)..F(Bi,0),F(A1,1)..F(Bi,1)) + 1.
另外，还有一点需要注意，就是 5 5 5中间的5 的处理。。。
具体代码如下：
AC代码：
复制内容到剪贴板
代码:
#include <iostream>
using namespace std;
int main(){
int n;
double Num[1000];
while(cin >> n){
for(int i = 0; i < n; ++i){
cin >> Num[i];
}
int Res[2001][3];
for(int i = 0; i < n; ++i){
Res[i][0] = 1;
Res[i][1] = 1;
Res[i][2] = 0;
}
for(int i = 0; i < n; ++i){
for(int k = 0; k < i; ++k){
if((Num[i] < Num[k]) || (!Res[k][2] && Num[i] == Num[k])){
if(Res[i][1] < Res[k][0] + 1){
Res[i][1] = Res[k][0] + 1;
Res[i][2] = 1;
}
if(Res[i][1] < Res[k][1] + 1){
Res[i][1] = Res[k][1] + 1;
Res[i][2] = 1;
}
}else if(Num[i] > Num[k]){
if(Res[i][0] < Res[k][0] + 1){
Res[i][0] = Res[k][0] + 1;
}
}
}
}
int max = 0;
for(int i = 0; i < n; ++i){
if(Res[i][0] > max){
max = Res[i][0];
}
if(Res[i][1] > max){
max = Res[i][1];
}
}
cout << n – max << endl;
}
}