信息学奥赛一本通T1260-拦截导弹

解题思路:

注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
int main(){
    // 定义数组a和b，长度为1100，n初始化为1，kkk初始化为-1
    int a[1100], b[1100], n = 1, kkk = -1;
    // 定义一个整型向量c
    vector<int> c;
    // 从标准输入读取数据到数组a中，直到输入结束，n记录元素个数
    while(cin >> a[n]) n++;
    // 调整n的值，使其表示实际元素个数
    n--;
    // 遍历数组a的每一个元素
    for(int i = 1; i <= n; i++){
        // 初始化b[i]为1
        b[i] = 1;
        // 内层循环，用于更新b[i]的值
        for(int j = 1; j < i; j++){
            // 如果a[j]大于等于a[i]，则更新b[i]为b[j]+1的最大值
            if(a[j] >= a[i]) b[i] = max(b[i], b[j] + 1);
        }
        // 更新kkk为当前最大值
        kkk = max(kkk, b[i]);
        // 标记变量s，用于判断是否找到合适的位置替换c中的元素
        int s = 0;
        // 遍历向量c，寻找可以替换的位置
        for(int j = 0; j < c.size(); j++){
            // 如果c[j]大于等于a[i]，则用a[i]替换c[j]，并设置s为1
            if(c[j] >= a[i]){
                c[j] = a[i];
                s = 1;
                break;
            }
        }
        // 如果拦截不到，则将a[i]添加到向量c中，及加一个系统
        if(s == 0){
            c.push_back(a[i]);
        }
    }
    // 输出结果：最长递增子序列的长度和向量c的大小,及最多能拦截的导弹数，最少要配备的系统数。
    cout << kkk << endl << c.size() << endl;
    return 0;
}