UVa 10534 – Wavio Sequence [DP水题]

Link

点击打开UVa题目链接

Mean

给定一个长度为N的整数序列,求一个最长子序列(不一定连续),使得该序列的长度为2K+1,前K+1个数严格递增,后K+1个数严格递减。

Analyse

最长上升子序列的变形,正反求两边,然后再扫一遍即可,具体看代码吧。时间复杂度为O(N*logN)

Code

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

const int maxn = 10240, inf = 0x3f3f3f3f;
int n, v[maxn], dp[maxn], s1[maxn], s2[maxn];

void solve() {
    memset(dp, inf, sizeof(dp));
    for(int i = 0; i < n; ++i)
        dp[s1[i] = (lower_bound(dp, dp+n, v[i]) - dp)] = v[i];
    memset(dp, inf, sizeof(dp));
    for(int i = n-1; i >= 0; --i)
        dp[s2[i] = (lower_bound(dp, dp+n, v[i]) - dp)] = v[i];
}

int main() {
    while(~scanf("%d", &n)) {
        for(int i = 0; i < n; ++i)
            scanf("%d", v + i);
        solve();
        int best = 1;
        for(int i = 0; i < n; ++i)
            best = max(best, min(s1[i], s2[i]) * 2 + 1);
        printf("%d\n", best);
    }
    return 0;
}

欢迎留言