题意简述
给定一个序列,问最少需要用多少个上升子序列或下降子序列就能覆盖整个序列
思路
这题的思路和拦截导弹那题的思路比较像,都是运用贪心算法来解。只不过拦截导弹那道题我们可以套用 Dilworth定理 的结论来直接写,而这道题需要我们爆搜每个点来进行判断这个点到底是放到上升子序列中好还是放到下降子序列中好。
由此,我们就可以建两个数组$\ up[\ ]\ $和$\ down[\ ]\ $来分别记录第$k$个上升或下降子序列的末尾元素,同时记录一下所有贪心中所得最小的答案,然后模拟一遍和“拦截导弹”那题一样的贪心思路即可。
P.S. 这题还有一个精髓的地方在于对$\ dfs\ $的剪枝处理很好地降低了这道题的时间复杂度。虽然表面上的时间复杂度是$\ O(N2^N)\ $但实际的时间复杂度远比这要小。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n;
int a[N];
int up[N], down[N];
int ans;
//u标识的是当前搜到了哪个数,su和sd分别表示当前上升子序列和下降子序列的个数
void dfs(int u, int su, int sd)
{
//剪枝,这样的话当我们得到了第一组解后就可以快速判断后面解的合理性
if(su + sd >= ans)
return;
//搜完的话就表示这次贪心是成功的,就更新一下ans
if(u == n)
{
ans = su + sd;
return;
}
//尝试把数放到下降子序列中
int k = 0;
while(a[u] > down[k] && k < sd)
k++;
int tmp = down[k];
down[k] = a[u];
//没新建子序列是一种情况,新建了sd就要+1
if(k < sd)
dfs(u + 1, su, sd);
else
dfs(u + 1, su, sd + 1);
//记得dfs的复原操作
down[k] = tmp;
//尝试把数放到上升子序列中
k = 0;
while(k < su && a[u] < up[k])
k++;
tmp = up[k];
up[k] = a[u];
if(k < su)
dfs(u + 1, su, sd);
else
dfs(u + 1, su + 1, sd);
up[k] = tmp;
}
int main()
{
while(cin >> n, n)
{
ans = n;
for(int i = 0; i < n; i++)
cin >> a[i];
dfs(0, 0, 0);
cout << ans << endl;
}
return 0;
}