nyoj 79-拦截导弹 (动态规划)
规划 动态 nyoj 79
2023-09-11 14:21:11 时间
79-拦截导弹
内存限制:64MB
时间限制:3000ms
特判: No
通过数:9
提交数:11
难度:3
题目描述:
某国为了防御敌国的导弹袭击,发展中一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于等于前一发的高度。某天,雷达捕捉到敌国导弹来袭。由于该系统还在试用阶段,所以只用一套系统,因此有可能不能拦截所有的导弹。
输入描述:
第一行输入测试数据组数N(1<=N<=10) 接下来一行输入这组测试数据共有多少个导弹m(1<=m<=20) 接下来行输入导弹依次飞来的高度,所有高度值均是大于0的正整数。
输出描述:
输出最多能拦截的导弹数目
样例输入:
2 8 389 207 155 300 299 170 158 65 3 88 34 65
样例输出:
6 2
分析:
1、与最长串类似的问题;
2、通过动态规划找出找出前面的最长组合;
3、依次往后考虑,得到的就是最优解(全局最长);
4、状态方程:dp[i] = max(dp[i], dp[j] + 1);
方法一:
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <queue> 9 #include <set> 10 11 using namespace std; 12 const int MAXN = 25; 13 14 int main() 15 { 16 int N; 17 scanf("%d", &N); 18 while(N --) 19 { 20 int n, a, A[MAXN], cnt = 0; 21 scanf("%d%d", &n, &A[0]); 22 while(-- n) 23 { 24 scanf("%d", &a); 25 if (A[cnt] > a) 26 A[++cnt] = a; 27 else 28 { 29 for(int i = 0; i <= cnt; ++ i) 30 if(A[i] <= a) 31 { 32 A[i] = a; 33 break; 34 } 35 } 36 } 37 printf("%d\n", cnt + 1); 38 } 39 return 0; 40 }
方法二:
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cmath> 6 #include <stack> 7 #include <map> 8 #include <queue> 9 #include <set> 10 11 using namespace std; 12 const int MAXN = 25; 13 14 int main() 15 { 16 int N; 17 scanf("%d", &N); 18 while(N --) 19 { 20 int n, a, A[MAXN], cnt = 0, dp[MAXN]; 21 scanf("%d", &n); 22 for(int i = 0; i < n; ++ i) 23 { 24 dp[i] = 1; 25 scanf("%d", &A[i]); 26 for(int j = 0; j < i; ++ j) 27 if (A[i] < A[j]) 28 dp[i] = max(dp[i], dp[j] + 1); 29 cnt = max(cnt, dp[i]); 30 } 31 printf("%d\n", cnt); 32 } 33 return 0; 34 }
相关文章
- 【UOJ#311】【UNR #2】积劳成疾(动态规划)
- 【UOJ#246】套路(动态规划)
- 【UOJ#340】【清华集训2017】小 Y 和恐怖的奴隶主(矩阵快速幂,动态规划)
- 【BZOJ1294】[SCOI2009]围豆豆(动态规划,状压)
- 【BZOJ1090】[SCOI2003]字符串折叠(动态规划)
- 【BZOJ1226】学校食堂(动态规划,状态压缩)
- 【BZOJ4300】绝世好题(动态规划)
- 【BZOJ4872】分手是祝愿(动态规划,数学期望)
- 【BZOJ2037】Sue的小球(动态规划)
- 【Luogu3041】视频游戏的连击(AC自动机,动态规划)
- 【算法】【递归与动态规划模块】两个字符串的公共最长子序列
- [matlab] 7.快速搜索随机树(RRT---Rapidly-exploring Random Trees) 路径规划
- 判断二叉树是否为平衡二叉树?树形DP,树形动态规划的递归套路
- 博文周刊第6期 | 程序员 30 岁前,该如何规划自己的职业发展?
- 强化学习代码实战-03动态规划算法(策略迭代)
- 《大型网站服务器容量规划》——3.4 通过回归方程规划容量
- [计蒜客(蓝桥杯省赛)]动态规划入门
- 动态规划dp算法经典包子凑数java
- Leetcode486之预测赢家(相关话题:动态规划,博弈论)
- LeetCode1143之最长公共子序列和最长公共子串(相关话题:动态规划)
- 173、【动态规划】leetcode ——300. 最长递增子序列 (C++版本)
- 153、【动态规划】leetcode ——1049. 最后一块石头的重量 II:滚动数组(C++版本)
- hdu 1087 Super Jumping! Jumping! Jumping!(动态规划DP)
- nyoj 16-矩形嵌套(贪心 + 动态规划DP)
- nyoj 17-单调递增最长子序列 && poj 2533(动态规划,演算法)