187. 导弹防御系统
题目链接
187. 导弹防御系统
为了对抗附近恶意国家的威胁,\(R\) 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如,一套系统先后拦截了高度为 \(3\) 和高度为 \(4\) 的两发导弹,那么接下来该系统就只能拦截高度大于 \(4\) 的导弹。
给定即将袭来的一系列导弹的高度,请你求出至少需要多少套防御系统,就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例,第一行包含整数 \(n\),表示来袭导弹数量。
第二行包含 \(n\) 个不同的整数,表示每个导弹的高度。
当输入测试用例 \(n=0\) 时,表示输入终止,且该用例无需处理。
输出格式
对于每个测试用例,输出一个占据一行的整数,表示所需的防御系统数量。
数据范围
\(1≤n≤50\)
输入样例:
5
3 5 2 4 1
0
输出样例:
2
样例解释
对于给出样例,最少需要两套防御系统。
一套击落高度为 \(3,4\) 的导弹,另一套击落高度为 \(5,2,1\) 的导弹。
解题思路
dfs,迭代加深
数据范围比较小,另外这里可上升可下降,不能用 \(LIS\) 来做,可考虑暴搜,但由于求最少,可用迭代加深来优化,另外需要注意dfs
的写法,放置某个导弹时,以上升序列为例,贪心思想,即放置在比当前导弹高度低且最大的序列后,但由于如果都没找到的话即当前导弹高度是最低的,即该序列单调下降的,从前枚举找到的第一个即为符合贪心策略的位置,下降序列同理
- 时间复杂度:\(O(n\times 2^n)\)
代码
// Problem: 导弹防御系统
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/189/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair PII;
typedef pair PLL;
template bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=55;
int n,h[N],up[N],down[N];
bool dfs(int u,int su,int sd,int depth)
{
if(sd+su>depth)return false;
if(u==n)return true;
bool f=true;
for(int i=0;iup[i])
{
int t=up[i];
up[i]=h[u];
if(dfs(u+1,su,sd,depth))return true;
up[i]=t;
f=false;
break;
}
if(f)
{
up[su]=h[u];
if(dfs(u+1,su+1,sd,depth))return true;
}
f=true;
for(int i=0;i