题目描述
为了对抗附近恶意国家的威胁,R国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为3和高度为4的两发导弹,那么接下来该系统就只能拦截高度大于4的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
输入格式
输入包含多组测试用例。对于每个测试用例,第一行包含整数n,表示来袭导弹数量。
第二行包含n个不同的整数,表示每个导弹的高度。
当输入测试用例n=0时,表示输入终止,且该用例无需处理。
输出格式
对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。
样例
数据范围
1≤n≤50
输入样例:
5
3 5 2 4 1
0
输出样例:
2
样例解释
对于给出样例,最少需要两套防御系统。
一套击落高度为3,4的导弹,另一套击落高度为5,2,1的导弹。
算法
(贪心 + 二分)
搜索顺序分为两个阶段:
从前往后枚举每颗导弹属于某个上升子序列,还是下降子序列;
如果属于上升子序列,则枚举属于哪个上升子序列(包括新开一个上升子序列);如果属于下降子序列,可以类似处理。
优化1:(贪心)
分别记录当前每个上升子序列的末尾数up[],和下降子序列的末尾数down[]。这样在枚举时可以快速判断当前数是否可以接在某个序列的后面。对于第二阶段的枚举,我们可以仿照上一题的贪心方式,对于上升子序列而言,我们将当前数接在最大的数后面,一定不会比接在其他数列后面更差。这是因为处理完当前数后,一定出现一个以当前数结尾的子序列,这是固定不变的,那么此时其他子序列的末尾数越小越好。
注意到按照这种贪心思路,up[]数组和down[]数组一定是单调的(up数组单调递减, down数组单调递增),因此在遍历时找到第一个满足的序列后就可以直接break了。
优化2: (二分)
枚举到的当前数接到上升子序列中:从up数组中找到一个小于当前数的最大值, up数组单调递减,因此可以用二分。注意:su表示up数组元素个数,结尾元素下标为su - 1(主要和check()函数有关), 因此, 当二分完成后如果r == su 表示up数组中元素都大于当前数,此时新开一个序列。否则,将当前数接到up[r] 的位置,即将这个序列的结尾元素更新为当前数。
枚举到的当前数接到上升子序列中:从down数组中找到一个大于当前数的最小值,down数组单调递增.注意:sd表示down数组元素个数,同时也表示数组结尾元素下标(主要和check()函数有关),因此,当二分完成后如果 l + 1 > su 表示down数组中元素都小于当前数,此时新开一个序列,否则,将当前数接到up[l + 1] 的位置,即将这个序列的结尾元素更新为当前数。
不同二分写法边界条件不一样!!下面代码给出了几种不同二分的写法。欢迎指正。。。。
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 55;
int up[N], down[N], h[N]; //分别存储上升子序列和下降子序列的结尾元素
int n;
int ans; //记录最小值
void dfs(int u, int su, int sd)
{
if(ans <= su + sd) return;
if(u == n)
{
ans = su + sd;
return;
}
//放在上升子序列中
//int k = 0;
//while(k < su && up[k] >= h[u]) k++;
int l1 = 0, r1 = su; //su表示down[]元素个数,结尾元素下标为su - 1
while(l1 < r1) //根据贪心,找到上升子序列中结尾元素小于当前元素的最大值
{
int mid = l1 + r1 >> 1;
if(up[mid] < h[u]) r1 = mid;
else l1 = mid + 1;
}
if(r1 < su) //su不是结尾元素下标 结尾元素下标是su-1; up[0]有意义
{
int t = up[r1];
up[r1] = h[u];
dfs(u + 1, su, sd);
up[r1] = t;
}
else //r1 = su
{
up[r1] = h[u]; //r1可以等于0 r1 < su ==> r1 与 su不会同步增加
dfs(u + 1, su + 1, sd);
}
//放在下降子序列中
// k = 0;
//while(k < sd && down[k] <= h[u]) k++;
//写法1:
/*int l = 0, r = sd; //sd表示down[]元素个数,结尾元素下标为sd
while(l < r) //根据贪心,找到下降子序列中结尾元素小于等于当前元素的最大值,二分结束后l+1一定大于当前元素
{
int mid = l + r + 1 >> 1;
if(down[mid] <= h[u]) l = mid;
else r = mid - 1;
}
if(l + 1 <= sd) //sd是结尾元素下标 down[0]无意义随便设一个较小值
{
int t = down[l + 1];
down[l + 1] = h[u];
dfs(u + 1, su, sd);
down[l + 1] = t;
}
else
{
down[l + 1] = h[u]; //l + 1 ,至少从1开始 此时状态l == su 即下标与元素个数同步增加
dfs(u + 1, su, sd + 1);
}*/
//写法2: 原理同上升序列
int l = 0, r = sd;
while(l < r) //根据贪心,找到下降子序列中结尾元素大于当前元素的最小值,二分结束后l一定大于当前元素
{
int mid = l + r >> 1;
if(down[mid] > h[u]) r = mid;
else l = mid + 1;
}
if(l < sd)
{
int t = down[l];
down[l] = h[u];
dfs(u + 1, su, sd);
down[l] = t;
}
else
{
down[l] = h[u]; //l 与 su不会同步增加
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;
}