算法思路
“至少需要多少多少套拦截系统”在AcWing 1010. 拦截导弹已经分析过了: 对于严格下降的导弹拦截系统, 其至少
需要系统的个数可以用LIS
求解, 本题在此基础上给了我们额外选择—拦截系统可以严格上升/
下降.
可以用dfs
搜索求解 : 每个导弹只有2
个选择, 把每种选择都搜索一遍即可.
不用bfs
的原因
-
空间太大. 需要保存每层的空间, 指数级别. 而
dfs
只保存线性路径. -
难以剪枝.
代码实现
全局变量保存最小值
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55, INF = 2e9;
int n;
int ans; //全局变量保存当前最优解
int a[N];
int up[N], down[N]; //分别保存LIS贪心算法的严格上升/下降序列
//u:当前遍历到的导弹a[u]; lu/ld : 序列当前的长度
void dfs(int u, int lu, int ld)
{
if( lu + ld >= ans )
{//剪枝 会减去很多不合理的拦截方案 虽然时间复杂度是指数级别 但剪枝操作极大降低了运行时间
return;
}
if( u == n )
{//遍历完毕
ans = lu + ld; //没被剪枝说明lu + ld < ans
return;
}
//将a[u]放入严格上升序列
int l = 0, r = lu;
while( l < r )
{
int mid = l + r + 1 >> 1;
if( up[mid] < a[u] ) l = mid;
else r = mid - 1;
}
r ++ ; //a[u]保存的位置
int t = up[r]; //暂时保存 为恢复现场
up[r] = a[u];
if( r <= lu ) dfs(u + 1, lu, ld);
else dfs(u + 1, lu + 1, ld); //长度需要更新
up[r] = t; //恢复现场
//将a[u]放入严格下降序列 代码与上面的对称
l = 0, r = ld;
while( l < r )
{
int mid = l + r + 1 >> 1;
if( down[mid] > a[u] ) l = mid;
else r = mid - 1;
}
r ++;
t = down[r];
down[r] = a[u];
if( r <= ld ) dfs(u + 1, lu, ld);
else dfs(u + 1, lu, ld + 1);
down[r] = t;
}
int main()
{
while( cin >> n, n )
{
for( int i = 0; i < n; i ++ ) cin >> a[i];
ans = n;
up[0] = -INF; down[0] = INF; //哨兵
dfs(0, 0, 0);
cout << ans << endl;
}
return 0;
}