UVA 1839 Alignment

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #define maxn 1005
 6 using namespace std;
 7 
 8 double d[maxn];
 9 int dp[maxn],dp2[maxn];
10 
11 int main (){
12     int n;
13     while (~scanf ("%d",&n)){
14         for (int i=0;i<n;i++)
15             scanf ("%lf",&d[i]);
16         int ans=0;
17         for (int i=0;i<n;i++){
18             dp[i]=1;
19             for (int j=0;j<i;j++){
20                 if (d[j]<d[i])
21                     dp[i]=max (dp[i],dp[j]+1);//求从左边开始的上升子序列；
22             }
23         }
24         for (int i=0;i<n/2;i++){
25             double temp;
26             temp=d[i];d[i]=d[n-i-1];d[n-i-1]=temp;//求逆序
27         }
28         for (int i=0;i<n;i++){
29             dp2[i]=1;
30             for (int j=0;j<i;j++){
31                 if (d[j]<d[i])
32                     dp2[i]=max (dp2[i],dp2[j]+1);//逆序的上升子序列，即原来的下降子序列；
33             }
34         }
35         for (int i=0;i<n;i++){
36             for (int j=0;j<n-i-1;j++){
37                 ans=max (ans,dp[i]+dp2[j]);//cout<<i<<":"<<dp[i]<<" "<<j<<":"<<dp2[j]<<endl;
38             }
39         }
40         printf ("%d
",n-ans);
41     }
42     return 0;
43 }