AcWing 187. 导弹防御系统
原题链接
中等
作者:
hai阿卢
,
2021-02-11 19:56:32
,
所有人可见
,
阅读 257
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int a[N],dw[N],up[N];
int n,ans;
void dfs(int u,int su,int sd)
{
if(su+sd>=ans) return;
if(u==n)
{
ans=sd+su;
}
int k=0;
while(k<su&&up[k]>=a[u]) k++;
int m=up[k];
up[k]=a[u];
if(k>=su) dfs(u+1,su+1,sd);
else dfs(u+1,su,sd);
up[k]=m;
k=0;
while(k<sd&&dw[k]<=a[u]) k++;
m=dw[k];
dw[k]=a[u];
if(k>=sd) dfs(u+1,su,sd+1);
else dfs(u+1,su,sd);
dw[k]=m;
}
int main()
{
while(cin>>n,n!=0)
{
for(int i=0;i<n;i++) cin>>a[i];
ans=n;
dfs(0,0,0);
cout<<ans<<endl;
}
return 0;
}