You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.
# include <bits/stdc++.h>
using namespace std ;
int a [ 101 ] = { 0 } ;
int dp1 [ 101 ] = { 0 } ;
int dp2 [ 101 ] = { 0 } ;
int main ( ) {
// 输入+输出重定向
freopen ( " ../1278.txt " , " r " , stdin ) ;
int n ;
cin > > n ;
for ( int i = 1 ; i < = n ; + + i ) {
cin > > a [ i ] ;
}
// 从左到右身高递增
for ( int i = 1 ; i < = n ; i + + ) { // 遍历每一个元素
dp1 [ i ] = 1 ; // 以这个元素结尾的dp数组, 默认值是1, 即表示只有它自己一个
for ( int j = 1 ; j < = i - 1 ; j + + ) { // 从比它小的每一个数都过来计算一次
// 找到比当前元素小的,并且以那个元素结尾的最长子序列长度+1比现在的大, 就是猴子选大王, 找最长的一条
if ( a [ i ] > a [ j ] & & dp1 [ j ] + 1 > dp1 [ i ] ) {
dp1 [ i ] = dp1 [ j ] + 1 ;
}
}
}
// 从右到左
// 从右到左进身高递增
for ( int i = n ; i > = 1 ; i - - ) {
dp2 [ i ] = 1 ;
for ( int j = i + 1 ; j < = n ; j + + ) {
if ( a [ j ] < a [ i ] & & dp2 [ j ] + 1 > dp2 [ i ] ) {
dp2 [ i ] = dp2 [ j ] + 1 ;
}
}
}
int removeCount = INF ;
for ( int i = 0 ; i < n ; i + + ) {
removeCount = min ( removeCount , n - ( dp1 [ i ] + dp2 [ i ] - 1 ) ) ;
}
cout < < removeCount < < endl ;
// 最后队列中有几个人设为m,则n-m就是出列的人员数量
// 而m是如何来的呢? max(dp1[i],dp2[i])的这个人
int maxx = - 1 ;
for ( int i = 1 ; i < = n ; + + i ) {
if ( dp1 [ i ] + dp2 [ i ] > maxx ) maxx = dp1 [ i ] + dp2 [ i ] - 1 ; // 之所以减1, 是因为有交集
}
cout < < n - maxx < < endl ;
// 关闭文件
fclose ( stdin ) ;
return 0 ;
}