AcWing 482. 合唱队形
原题链接
中等
作者:
yi生守护你
,
2022-05-10 13:53:32
,
所有人可见
,
阅读 173
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int w[N];
int s[N], d[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++)
{
s[i] = 1;
for (int j = 1; j < i; j++)
if (w[i] > w[j])
s[i] = max(s[i], s[j] + 1);
}
for (int i = n; i ; i--)
{
d[i] = 1;
for (int j = n; j > i; j--)
if (w[i] > w[j])
d[i] = max(d[i], d[j] + 1);
}
int ans = 0;
for (int i = 0; i <= n; i++)
ans = max(ans, s[i] + d[i] - 1);
ans = n - ans;
cout << ans << "\n";
return 0;
}