1 /* 2 Problem: 1836        User: bibier 3 Memory: 712K        Time: 63MS 4 Language: G++        Result: Accepted 5 */ 6 //动态规划 之 双向LIS问题 7 #include <stdio.h> 8 #include <string.h> 9 #include <iostream>10 #include <algorithm>11 #include <cstdio>12 #include <cstring>13 #include <cmath>14 #include <stack>15 #include <queue>16 #include <vector>17 using namespace std;18 #define M 0x0f0f0f0f19 #define min(a,b) (a>b?b:a)20 #define max(a,b) (a>b?a:b)21 22 int qdp[1003];23 int hdp[1003];24 float high[1003];25 26 int main()27 {28     int n;29     int i,j;30     scanf("%d",&n);31     for(i=0; i<n; i++)32     {33         scanf("%f",&high[i]);34         qdp[i]=1;35         hdp[i]=1;36     }37 38     for(i=1; i<n; i++)39         for(j=0; j<i; j++)40         {41             if(high[j]<high[i]&&qdp[j]==qdp[i])42                 qdp[i]++;43         }44 45     for(i=n-2; i>=0; i--)46         for(j=n-1; j>i; j--)47         {48             if(high[j]<high[i]&&hdp[j]==hdp[i])49                 hdp[i]++;50         }51 52     int max_=0;53     54     /*55     若没有身高相同的一层循环就足够56     for(i=0; i<n; i++)57         max_=max(max_,qdp[i]+hdp[i]);58     */59     60     for(i=0; i<n-1; i++)   //用两层循环是为了处理1 2 5 5 1 3 2或1 2 5 5 5 5 1 3 261         for(j=i+1; j<n; j++)62             max_=max(max_,qdp[i]+hdp[j]);63     printf("%d\n",n-max_);64     return 0;65 }