hdu 1257 最少拦截系统 求连续递减子序列个数 (理解二分)
2023-09-14 08:56:55 时间
最少拦截系统
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 68249 Accepted Submission(s): 26499
Problem Description
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.
Input
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)
Output
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.
Sample Input
8
389 207 155 300 299 170 158 65
Sample Output
2
题意:给定的序列可以分成几个递减子序列
#include<iostream> using namespace std; int a[30005], b[30005]; int n; int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; i++) { cin >> a[i]; } int k = 1; b[1] = 999999; for (int i = 0; i < n; i++) { for (int j = 1; j <= k; j++) { if (b[j] >= a[i]) { b[j] = a[i]; break; } else if (j == k) { k++; b[k] = a[i]; break; } } } cout << k << endl; } return 0; }
相关文章
- SIGIR'21 因果推断+推荐系统:利用反事实理论增强用户行为序列数据
- 导弹防御系统(dfs+最长上升子序列)
- Redis 时间序列
- 求栅格序列每个像元的变化趋势和对应P值
- 用LASSO,adaptive LASSO预测通货膨胀时间序列|附代码数据
- 剑指44-翻转单词顺序序列
- 【数字信号处理】序列傅里叶变换 ( 基本序列的傅里叶变换 | 求 cosωn 的傅里叶变换 | 复变函数欧拉公式 )
- 【数字信号处理】傅里叶变换性质 ( 共轭对称、共轭反对称 与 偶对称、奇对称关联 | 序列对称分解定理 )
- 在Redis中如何保存时间序列数据详解
- Oracle自动序列:实现快速自增长(oracle自动序列)
- Oracle为表创建序列利用最大效率获取ID(oracle为表建立序列)
- 研究Oracle中序列的编写方法(oracle中的序列编写)
- AI营销的下一战场:利用时间序列和空间轨迹探索用户未知需求
- PHP下通过系统信号量加锁方式获取递增序列ID