《算法提高课》题解与笔记上线啦！(链接就是这个){: style=”color: #FF0000”}

创建时间2024-1-23

$$ #2 1010.拦截导弹 $$

最长上升子序列模型

原题Link

Code:

# include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, ans, cnt;
int h[N], f[N], g[N];

int main(){
    n = 1;
    while(scanf("%d", &h[n]) == 1) n ++;
    n --;

    for(int i = 1; i <= n; i ++){
        f[i] = 1;
        for(int j = 1; j < i; j ++)
            if(h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);

        ans = max(ans, f[i]);
    }

//  for(int i = 1; i <= n; i ++){ // 对于每个导弹而言 
//      int k = 1;
//      while(k <= cnt && g[k] < h[i]) k ++; // 遍历系统找到第一个大于等于他的系统 
//      g[k] = h[i]; // 更新高度 
//      if(k > cnt) cnt ++; // 没找到,新建 
//  }

    for(int i = 1; i <= n; i ++){
        int l = 1, r = cnt;
        while(l < r){
            int mid = l + r >> 1;
            if(g[mid] < h[i]) l = mid + 1;
            else r = mid;
        }

        if(g[l] >= h[i]) g[l] = h[i];
        else g[++ cnt] = h[i];
    }

    printf("%d\n%d", ans, cnt);

    return 0;
}