首页 > 代码库 > UVA 1839 Alignment

UVA 1839 Alignment

2024-07-14 21:55:43   216人阅读

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

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

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

 

 

 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",n-ans);41     }42     return 0;43 }

 


联系
我们