思路: 最长上升子序列
分析:
1 题目要求最少的出队的人数,那么就是要求一个i使得满足的人数最多
2 很明显如果我们单独看i这个人,那么他就是中间点左边满足递增,右边满足递减。
3 很明显的一道最长上升子序列问题,我们通过枚举中间人i,然后去求左右满足的人数,最后求最大的满足人数就可以得到最少的出队人数
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 110;
int ans , n , num[MAXN];
int dp[MAXN];
int solve(){
int ans = 1;
//枚举中间点
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= i ; j++){
dp[j] = 1;
for(int k = 1 ; k < j ; k++)
if(num[k] < num[j])
dp[j] = max(dp[j] , dp[k]+1);
}
int sum1 = dp[i];
for(int j = n ; j >= i ; j--){
dp[j] = 1;
for(int k = n ; k > j ; k--)
if(num[k] < num[j])
dp[j] = max(dp[j] , dp[k]+1);
}
int sum2 = dp[i];
ans = max(ans , sum1+sum2-1);
}
return n-ans;
}
int main(){
while(scanf("%d" , &n) != EOF){
for(int i = 1 ; i <= n ; i++)
scanf("%d" , &num[i]);
printf("%d\n" , solve());
}
return 0;
}