算法: 贪心 + dfs + dp

思路,其他题解已经说的很清楚了, 我在这里想补充之前没想明白的一个点.
如下图: y总,在提高课里讲的 up[k] >= q[u] 是上升子序列 down[k] <= q[u] 是下降子序列

所以up对应的上升子序列结尾 down对应的下降子序列结尾 没有反.
但其实up和down选择的机会是一样的,即使是反着存,输出答案也是正确的.

时间复杂度

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 55;
int q[N], up[N], down[N];
int ans, n;

void dfs(int u, int st, int ed) {
    if (st + ed >= ans) return;
    if (n == u) {
        ans = st + ed;
        return;
    }
    int k = 0;
    while (k < st && up[k] >= q[u]) k++;
    int t = up[k];
    up[k] = q[u];
    if (k == st) dfs(u + 1, st + 1, ed);
    else dfs(u + 1, st, ed);
    up[k] = t;

    k = 0;
    while (k < ed && down[k] <= q[u]) k++;
    t = down[k];
    down[k] = q[u];
    if (k == ed) dfs(u + 1, st, ed + 1);
    else dfs(u + 1, st, ed);
    down[k] = t;
}

int main(void) {
    while (cin >> n, n) {
        for (int i = 0; i < n; i++) cin >> q[i];
        ans = n;
        dfs(0, 0, 0);

        cout << ans << endl;
    }
    return 0;
}