AcWing 482. 合唱队形
原题链接
中等
作者:
自律
,
2021-08-17 08:25:39
,
所有人可见
,
阅读 186
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int a[N];
int f[N],g[N];
int n;
int main()
{
cin>>n;
for(int i = 1;i <= n;i ++) cin>>a[i];
for(int i = 1;i <= n;i ++)
{
f[i] = 1; //初始状态设为1,为了特判所有的a[j]都大于a[i]的情况
for(int j = 1;j <= i;j ++)
if(a[j] < a[i])
f[i] = max(f[i],f[j] + 1);
}
for(int i = n;i >= 1;i --) //i倒着循环 保证更新迭代g[i]时所用到的后边的数据已经被更新过
{
g[i] = 1;
for(int j = i;j <= n;j ++)
if(a[j] < a[i])
g[i] = max(g[i],g[j] + 1);
}
int res = 0;
for(int i = 1;i <= n;i ++)
res = max(res,f[i] + g[i] - 1); //因为峰值点计入两次 所以-1
cout<<n - res<<endl;
return 0;
}