csu 1551: Longest Increasing Subsequence Again BIT + 思维

预处理last[i]表示以第i个开始，的合法后缀。

pre[i]表示以第i个结尾，的合法前缀。

那么每一个数a[i]，肯定是一个合法后缀last[i] + 一个合法前缀，那么合法前缀的数字要小于a[i]，并且最大，bit维护小于等于val的最大值即可。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
const int maxn = 1e4 + 20;
int c[maxn];
int lowbit(int x) {
    return x & (-x);
}
void upDate(int pos, int val) {
    while (pos <= maxn - 20) {
        c[pos] = max(c[pos], val);
        pos += lowbit(pos);
    }
}
int ask(int pos) {
    int ans = 0;
    while (pos) {
        ans = max(ans, c[pos]);
        pos -= lowbit(pos);
    }
    return ans;
}
int a[maxn];
int n;
int last[maxn], pre[maxn];
void work() {
    memset(c, 0, sizeof c);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    last[n] = 1;
    for (int i = n - 1; i >= 1; --i) {
        if (a[i] < a[i + 1]) {
            last[i] = last[i + 1] + 1;
        } else last[i] = 1;
    }
    pre[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] > a[i - 1]) {
            pre[i] = pre[i - 1] + 1;
        } else pre[i] = 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, last[i] + ask(a[i] - 1));
        upDate(a[i], pre[i]);
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    IOS;
    while (cin >> n) work();
    return 0;
}

View Code