AcWing 187. 导弹防御系统
原题链接
中等
作者:
wangyj
,
2021-01-12 18:04:00
,
所有人可见
,
阅读 338
#include<iostream>
#include<algorithm>
using namespace std;
int n,h[55],up[55],down[55],ans;
void dfs(int u, int su, int sd)
{
if(su+sd>=ans)return;
if(u==n){
ans=min(ans,su+sd);
return;
}
int k=0;
while(k<su&&up[k]>=h[u])k++;
if(k<su){
int t=up[k];
up[k]=h[u];
dfs(u+1,su,sd);
up[k]=t;
}
else{
up[k]=h[u];
dfs(u+1,su+1,sd);
}
k=0;
while(k<sd&&down[k]<=h[u])k++;
if(k<sd){
int t=down[k];
down[k]=h[u];
dfs(u+1,su,sd);
down[k]=t;
}
else{
down[k]=h[u];
dfs(u+1,su,sd+1);
}
}
int main()
{
while (cin>>n,n){
for(int i=0;i<n;i++)cin>>h[i];
ans=n;
dfs(0,0,0);
cout<<ans<<endl;
}
return 0;
}