题解 | 拦截导弹

#include <stdio.h>
#include <stdlib.h>
int main() {
    int n;
    int system_count = 0;
    scanf("%d", &n);
    int system[n];
    int* arr = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] >= arr[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }
    int max = dp[0];
    for (int j = 0; j < n; j++) {
        if (dp[j] > max) {
            max = dp[j];
        }
    }

    for (int i = 0; i < n; i++) {
        int flag = 0;
        for (int j = 0; j < system_count; j++) {
            if (system[j] >= arr[i]) {
                system[j] = arr[i];
                flag = 1;
                break;

            }
        }
        if (!flag) {
            system[system_count++]=arr[i];
        }
    }
    printf("%d\n%d\n", max,system_count);
    return 0;
}