题解 P6564 「POI2007」堆积木KLO

给出长为 n 的序列 a，求一个 a 的子序列 b，最大化 \(\sum_{i}^{k}[b_i=i]\)。

思路

DP 时，如果点 \(i\) 能从点 \(j\) 转移过来，满足条件： \[ \begin{align} i&>j\\ a_i&> a_j\\ a_i-a_j&\le i-j \end{align} \] 满足后两个条件时一定满足第一个条件。

转化为 \(a_i>a_j,i-a_i\ge j-a_j\)，二维偏序直接上 CDQ。

懒得归并，复杂度 \(O(n\log^2n)\)。

因为一个 \(>\) 一个 \(\ge\)，所以 \(i-a_i\) 属性要作第一维。

代码

记得加个 0 点。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

template<typename T> inline void read(T &x) {}

const int N = 1e5 + 9;

struct Data {
    int id, x, y;
};

int n;
Data a[N];
int f[N];

bool cmpx(const Data &x, const Data &y) {
    if (x.x == y.x) return x.y < y.y;
    return x.x < y.x;
}
bool cmpy(const Data &x, const Data &y) {
    if (x.y == y.y) return x.x < y.x;
    return x.y < y.y;
}

inline void CDQ(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    sort(a+l, a+mid+1, cmpy);
    CDQ(l, mid);
    sort(a+l, a+mid+1, cmpx), sort(a+mid+1, a+r+1, cmpx);
    int pl = l, pr = mid + 1, ma = -INF;
    while (pr <= r) {
        while (pl <= mid && a[pl].x < a[pr].x)
            ma = max(ma, f[a[pl].id]), pl++;
        // 当 i - a[i] < 0 时，该点一定不满足
        if (a[pr].y >= 0) f[a[pr].id] = max(f[a[pr].id], ma + 1);
        pr++;
    }
    sort(a+mid+1, a+r+1, cmpy);
    CDQ(mid+1, r);
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)
        read(a[i].x), a[i].y = i - a[i].x, a[i].id = i;
    a[++n] = (Data){ 0, 0, 0 };
    sort(a+1, a+n+1, cmpy);
    CDQ(1, n);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}