秋招算法——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 ++;
//
//    }
//}

分析总结

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

原文地址：https://blog.csdn.net/Blackoutdragon/article/details/138818171

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！