最好的网站推广,新乡哪里有做网站的,成都网站建设方案外包,不忘初心 继续前进网站怎么做概览检索 动态规划DP 最长上升子序列模型 导弹防御系统
原题链接
AcWiing 187. 导弹防御系统
题目描述
为了对抗附近恶意国家的威胁#xff0c;R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如#xff0… 概览检索 动态规划DP 最长上升子序列模型 导弹防御系统
原题链接
AcWiing 187. 导弹防御系统
题目描述
为了对抗附近恶意国家的威胁R国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如一套系统先后拦截了高度为 3和高度为 4的两发导弹那么接下来该系统就只能拦截高度大于 4的导弹。
给定即将袭来的一系列导弹的高度请你求出至少需要多少套防御系统就可以将它们全部击落。
输入格式 输入包含多组测试用例。 对于每个测试用例第一行包含整数 n表示来袭导弹数量。 第二行包含 n个不同的整数表示每个导弹的高度。 当输入测试用例 n0时表示输入终止且该用例无需处理。
输出格式 对于每个测试用例输出一个占据一行的整数表示所需的防御系统数量。
数据范围 1≤n≤50
输入样例
5
3 5 2 4 1
0 输出样例
2样例解释 对于给出样例最少需要两套防御系统。 一套击落高度为 3,4的导弹另一套击落高度为 5,2,1的导弹。
题目分析
DFS暴搜最长上升子序列模型 最长上升子序列模型部分参考 拦截导弹。
完整代码
#include iostream
#include algorithm
using namespace std;
const int N55;
int n;
int a[N];
int up[N],down[N];
int ans;
/*DFS暴搜*/
//su为拦截上升高度的系统数sd为拦截下降高度的系统数
void dfs(int u,int su,int sd){//当前解比当前全局最优解ans大直接returnif(susdans) return;//如果遍历到最后一个数值计算结束returnif(un){anssusd;return;}//情况1将当前数放到上升子序列中int k0;while(ksuup[k]a[u]) k; //找到一个序列结尾数小于当前数的序列int tup[k]; //t保存原先序列结尾数up[k]a[u]; //将当前数放在该序列后更新结尾数if(ksu) dfs(u1,su,sd); //找到了符合条件的序列else dfs(u1,su1,sd); //未找到符合条件的序列新建序列序列数su1up[k]t; //回溯为原先状态//情况2将当前数放到下降子序列中k0;while(ksddown[k]a[u]) k;tdown[k];down[k]a[u];if(ksd) dfs(u1,su,sd);else dfs(u1,su,sd1);down[k]t;
}
int main(){while(cinn,n){for(int i0;in;i) cina[i];ansn;dfs(0,0,0);coutansendl;}return 0;
}
