拦截导弹 OpenJ_Bailian - 2945 (DP最长下降子列)

朴灿烈づ我的快乐病毒、 2022-02-25 02:26 56阅读 0赞

某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,并观测到导弹依次飞来的高度,请计算这套系统最多能拦截多少导弹。拦截来袭导弹时,必须按来袭导弹袭击的时间顺序,不允许先拦截后面的导弹,再拦截前面的导弹。

Input

输入有两行,
第一行,输入雷达捕捉到的敌国导弹的数量k(k<=25),
第二行,输入k个正整数,表示k枚导弹的高度,按来袭导弹的袭击时间顺序给出,以空格分隔。

Output

输出只有一行,包含一个整数,表示最多能拦截多少枚导弹。

Sample Input

  1. 8
  2. 300 207 155 300 299 170 158 65

Sample Output

  1. 6

解题思路:

求最长的下降子序列即可

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. const int MAXN = 30; //导弹数量30个
  5. int arr[MAXN];
  6. int k;
  7. int adp[MAXN];
  8. int main() {
  9. cin >> k;
  10. for (int i = 0; i < k; ++i) {
  11. cin >> arr[i]; //先初始化值
  12. adp[i] = 1; //注意要赋初值
  13. }
  14. adp[0] = 1;
  15. for (int i = 1; i < k; ++i) {
  16. for (int j = 0; j < i; ++j) { //不以i为终点
  17. if (arr[i] <= arr[j]) {
  18. adp[i] = max(adp[i], adp[j] + 1);
  19. }
  20. }
  21. }
  22. cout << *max_element(adp, adp + k) << endl;
  23. system("PAUSE");
  24. return 0;
  25. }

发表评论

表情:
评论列表 (有 0 条评论,56人围观)

还没有评论,来说两句吧...

相关阅读

    相关 NOIP 1999 导弹拦截(DP)

    题目描述: 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度

    相关 下降序列

    定义:  设有由n个不相同的整数组成的数列,记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 例如3,18,7,14,10,12,23,41,1