每个点都爆模一下,竟然过了。。。
时间复杂度超O(n2)
请求加强数据
#include<bits/stdc++.h>
using namespace std;
int n;
int arr[10000000];
int dp[10000000];
int main()
{
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", arr+i);
int maxx = 0;
for(int j=2; j<=n; j++)
{
int tmp = 0;
int len = 1;
dp[1] = arr[1];
for(int i=2; i<=j-1; i++)
{
int t = lower_bound(dp+1, dp+len+1, arr[i])-dp;
dp[t] = arr[i];
if(len < t) len++;
}
tmp += len;
memset(dp, 0, sizeof(dp));
len = 1;
dp[1] = arr[j];
for(int i=j; i<=n; i++)
{
int t = lower_bound(dp+1, dp+len+1, arr[i], greater<int>())-dp;
dp[t] = arr[i];
if(len < t) len++;
}
tmp += len;
maxx = max(tmp, maxx);
}
printf("%d", n-maxx);
return 0;
}