题目描述
给一个序列,需要用最少的不上升(或不下降)子序列覆盖掉整个序列。
输入格式
输入包含多组测试用例。
对于每个测试用例,第一行包含整数n,表示来袭导弹数量。
第二行包含n个不同的整数,表示每个导弹的高度。
当输入测试用例n=0时,表示输入终止,且该用例无需处理。
样例
5
3 5 2 4 1
0
这里需要用到贪心的方法,利用up[]和down[]存储每个上升(或下降)子序列的最后一个数。之后按照每个数进行更新
这里会用到暴力搜索dfs。详情请看yxc的视频讲解。
算法1
(迭代加深) $O(n2^n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 60;
int n;
int h[N];
int up[N], down[N];
bool dfs(int depth, int u, int su, int sd)
{
// 如果上升序列个数 + 下降序列个数 > 总个数是上限,则回溯
if (su + sd > depth) return false;
if (u == n) return true;
// 枚举放到上升子序列中的情况
bool flag = false;
for (int i = 1; i <= su; i ++ )
if (up[i] < h[u])
{
int t = up[i];
up[i] = h[u];
if (dfs(depth, u + 1, su, sd)) return true;
up[i] = t;
flag = true;
break; // 注意由上述证明的贪心原理,只要找到第一个可以放的序列,就可以结束循环了
}
if (!flag) // 如果不能放到任意一个序列后面,则单开一个新的序列
{
up[su + 1] = h[u];
if (dfs(depth, u + 1, su + 1, sd)) return true;
}
// 枚举放到下降子序列中的情况
flag = false;
for (int i = 1; i <= sd; i ++ )
if (down[i] > h[u])
{
int t = down[i];
down[i] = h[u];
if (dfs(depth, u + 1, su, sd)) return true;
down[i] = t;
flag = true;
break; // 注意由上述证明的贪心原理,只要找到第一个可以放的序列,就可以结束循环了
}
if (!flag) // 如果不能放到任意一个序列后面,则单开一个新的序列
{
down[sd + 1] = h[u];
if (dfs(depth, u + 1, su, sd + 1)) return true;
}
return false;
}
int main()
{
while (cin >> n, n)
{
for (int i = 0; i < n; i ++ ) cin >> h[i];
int depth = 0;
while (!dfs(depth, 0, 0, 0)) depth ++ ; // 迭代加深搜索,这里的depth代表子序列个数的上限
cout << depth << endl;
}
return 0;
}
算法2
(记录全局最小量) $O(n2^n)$
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
int n;
int a[N];
int up[N],down[N];
int ans;
void dfs(int u,int su,int sd)
{
if(su + sd >= ans)
return;
if(u == n)
{
ans = su + sd;
return;
}
int k = 0;
while(k < su && up[k] >= a[u])
k++;
int t = up[k];
up[k] = a[u];
if(k < su)
dfs(u + 1,su,sd);
else
dfs(u + 1,su + 1,sd);
up[k] = t;
k = 0;
while(k < sd && down[k] <= a[u])
k++;
t = down[k];
down[k] = a[u];
if(k < sd)
dfs(u + 1,su,sd);
else
dfs(u + 1,su,sd + 1);
down[k] = t;
}
int main()
{
while(cin >> n,n)
{
for(int i = 0;i < n;i++)
cin >> a[i];
ans = n;
dfs(0,0,0);
cout << ans << endl;
}
return 0;
}