UVA 1839 Alignment

还是最长上升子序列。。。

本题是求队列中任一士兵都能从左边或者右边看到队伍外；

即某一士兵左边为上升子序列，右边为下降子序列。求两个序列和，再用总数减去；

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 #define maxn 1005

 using namespace std;

 double d[maxn];

 int dp[maxn],dp2[maxn];

 int main (){

     int n;

     while (~scanf ("%d",&n)){

         for (int i=;i<n;i++)

             scanf ("%lf",&d[i]);

         int ans=;

         for (int i=;i<n;i++){

             dp[i]=;

             for (int j=;j<i;j++){

                 if (d[j]<d[i])

                     dp[i]=max (dp[i],dp[j]+);//求从左边开始的上升子序列；

             }

         }

         for (int i=;i<n/;i++){

             double temp;

             temp=d[i];d[i]=d[n-i-];d[n-i-]=temp;//求逆序

         }

         for (int i=;i<n;i++){

             dp2[i]=;

             for (int j=;j<i;j++){

                 if (d[j]<d[i])

                     dp2[i]=max (dp2[i],dp2[j]+);//逆序的上升子序列，即原来的下降子序列；

             }

         }

         for (int i=;i<n;i++){

             for (int j=;j<n-i-;j++){

                 ans=max (ans,dp[i]+dp2[j]);//cout<<i<<":"<<dp[i]<<" "<<j<<":"<<dp2[j]<<endl;

             }

         }

         printf ("%d\n",n-ans);

     }

     return ;

 }