array array array

【2017 ACM/ICPC Asia Regional Shenyang Online】array array array

Solution:

反过来找最长不上升子序列的长度,就是正着找最长不下降子序列的长度,所以这道题其实就是找两次最长不上升子序列,注意,\(O(n^2)\)会超时。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e5 + 10;
int arr[LIM];
int rarr[LIM];
int dp[LIM];
int rdp[LIM];
int n;

inline int maxi(int a, int b) {
    return a > b ? a : b;
}

int lis() {
    memset(dp, 0, sizeof dp);
    memset(rdp, 0, sizeof rdp);
    int dpl, rdpl;
    dpl = rdpl = 0;
    for (int i = 0; i < n; i++) {
        int j;
        for (j = 0; j < dpl; j++) {
            if (arr[i] > dp[j]) {
                dp[j] = arr[i];
                break;
            }
        }
        if (j == dpl) dp[dpl++] = arr[i];
        for (j = 0; j < rdpl; j++) {
            if (rarr[i] > rdp[j]) {
                rdp[j] = rarr[i];
                break;
            }
        }
        if (j == rdpl) rdp[rdpl++] = rarr[i];
    }
    return maxi(dpl, rdpl);
}

int main(void) {
    int t, k;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", arr + i);
            rarr[n - i - 1] = arr[i];
        }
        int maxi = lis();
        printf("%s\n", maxi >= n - k ? "A is a magic array." : "A is not a magic array.");
    }
    return 0;
}