AcWing 187. 导弹防御系统
原题链接
中等
作者:
小.bug
,
2022-05-16 18:00:24
,
所有人可见
,
阅读 99
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N],up[N],down[N];
int n;
int res;
void dfs(int u, int up_cnt, int down_cnt)
{
if(up_cnt + down_cnt >= res) return;
if(u > n)
{
res = up_cnt + down_cnt;
return;
}
int k;
//加入上升子序列
k = 0;
while(up[k] <= a[u] && k < up_cnt) k++;
//没找到
if(k == up_cnt)
{
up[k] = a[u];
dfs(u + 1, up_cnt + 1, down_cnt);
}
//找到了
else
{
int t = up[k];
up[k] = a[u];
dfs(u + 1, up_cnt, down_cnt);
up[k] = t;
}
//加入下降子序列
k = 0;
while(down[k] >= a[u] && k < down_cnt) k++;
if(k == down_cnt)
{
down[k] = a[u];
dfs(u + 1, up_cnt, down_cnt + 1);
}
else
{
int t = down[k];
down[k] = a[u];
dfs(u + 1, up_cnt, down_cnt);
down[k] = t;
}
}
int main()
{
while(cin >> n && n)
{
res = n;
for(int i = 1; i <= n; i++) cin >> a[i];
dfs(1,0,0);
cout << res << endl;
}
return 0;
}