题意简述
同AcWing 1014. 登山。只不过这里要求的是最少删去多少个元素能够得到一个如同AcWing 1014. 登山题目所要求的子序列。
思路
题目一样,思路也一样。
我们求得AcWing 1014. 登山中的答案后用$\ n\ $减一下就可以了。
复杂度分析
- 时间复杂度:$O(N^2)$
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int f1[N], f2[N];
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= n; i++)
{
f1[i] = 1;
for(int j = i - 1; j; j--)
if(a[i] > a[j])
f1[i] = max(f1[i], f1[j] + 1);
}
for(int i = n; i; i--)
{
f2[i] = 1;
for(int j = i + 1; j <= n; j++)
if(a[i] > a[j])
f2[i] = max(f2[i], f2[j] + 1);
}
int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans, f1[i] + f2[i] - 1);
cout << n - ans << endl;
return 0;
}