秋招算法——AcWing101——拦截导弹

题目描述

思路分析

• 目前是有一个笨办法，就是创建链表记录每一个最长下降子序列所对应的节点的链接，然后逐个记录所有结点的访问情况，直接所有节点都被访问过。
• 这个方法不是很好，因为需要计算很多次，会超时，这里用了贪心的方法来证明，虽然不是最优子序列，但是数量是一致的。

实现源码

#include <iostream>
#include <algorithm>
#include <sstream>using namespace std;const int K = 110;
const int N = 110;
const int H = 12000;
int h[H];
int Up[N];
int Down[N];
struct Node {int idx;Node *next;
};
bool DownAcess[N];
Node DownRecord[N];  // 记录下降节点的序列int main() {int n = 1;string line;getline(cin,line);stringstream ss(line);while(ss>>h[n]) n++;n --;int times = 0;bool endFlag = true ;
//    while(endFlag){
//        endFlag = false;
//        times ++;
//        int maxIdx = 1;
//        int maxNum = 0;// 计算最长上升子序列int res = 0;for (int i = n; i >= 1; -- i) {Down[i] = 1;DownRecord[i].idx = i;// 右侧最长上升子序列for (int k = n; k > i ; --k) {if (h[k] <= h[i]){Down[i] = max(Down[i], Down[k] + 1);if (Down[i] < Down[k] + 1)DownRecord[i].next = &DownRecord[k];}}res = max(res, Down[i]);}cout<<res<<endl;
//
//        for (int i = 1; i <= n; ++i) {
//            if (maxNum < Down[i]) {
//                maxIdx = i;
//            }
//        }
//
//        Node *temp = &DownRecord[maxIdx];
//        while(temp != NULL){
//            DownAcess[temp->idx]  = true;
//        }
//
//        for (int i = 1; i <= n; ++i) {
//            if (DownAcess[i] == false) endFlag = true;
//        }//    }
//    cout<<times<<endl;return 0;
}
//  正解
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 1005;
//int n;
//int q[N];
//int f[N],g[N]
//
//int main()
//{
//    while(cin>> q[n])  n ++;
//    int res = 0;
//    for (int i = 0; i < n; ++i) {
//        for (int j = 0; j < i; ++j) {
//            if (q[j] <= q[i])
//                f[i] = max(f[i],f[j] + 1);
//        }
//        res = max(res,f[i]);
//    }
//    cout<<res<<endl;
//
//    int cnt = 0;
//    for(int i = 0;i < n;i ++){
//        int k = 0;  // 维护的索引的序列
//        while(k < cnt && g[k] < q[i]) k ++;  // 遍历的每一个维护的最大的序列值
//        g[k] = q[i];
//        if(k >= cnt) cnt ++;
//
//    }
//}

分析总结

• 这里的证明看的不是很懂，但是用样例推过了，确实是正确的。使用贪心求最少的子序列数量，和两次最优子序列是相同的。
• 但是如果确实想不起来，确实可以使用这个方法进行实验。