【DP】#1109. [POI2007]堆积木Klo

https://darkbzoj.cc/problem/1109

分析

考虑状态表示原来在位置 \(i\) 的数有贡献（也就是说在结束操作后它的位置 \(i'\) 满足 \(i'= w_i\)）的最大值为 \(f[i]\)。

那么我们有转移方程 \(f[i] = \max f[j] + 1\)，其中 \((j<i, ~ w_j<w_i, ~ w_i-w_j\leq i-j)\)。

考虑优化转移：

\(w_i-w_j \leq i-j\) 也就是 \(j-w_j \leq i-w_i\)。

可以发现 \(w_j<w_i, ~ j-w_j \leq i-w_i\) 同时满足的时候第一个约束也必然满足，所以只需要考虑这两个约束。

因为 \(j-w_j \leq i-w_i\) 有等号，为了消除等号的影响，考虑根据 \(j-w_j < i-w_i\) 为第一关键字，下标为第二关键字进行排序。

排序后使用后缀数组维护 \(w_j<w_i\) 的贡献即可。

#include<bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << ": " << (x) << endl
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
 
#define x first
#define y second
using pii = pair<int, int>;
using ll = long long;
 
inline void read(int &x){
    int s=0; x=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-')x=-1;ch=getchar();}
    while(ch>='0' && ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
    x*=s;
}

const int N=1e6+5;

int n;

struct Node{
	int id, w;
	
	bool operator < (const Node &o)const{
		return id-w==o.id-o.w? id<o.id: id-w<o.id-o.w;
	}
}w[N];

int tr[N];

int lowbit(int x){
	return x&-x;
}

void upd(int x, int k){
	for(; x<N; x+=lowbit(x)) tr[x]=max(tr[x], k);
}

int query(int x){
	int res=0;
	for(; x; x-=lowbit(x)) res=max(res, tr[x]);
	return res;
}

signed main(){
	cin>>n;
	rep(i,1,n){
		int x; read(x);
		w[i]={i, x};
	}
	sort(w+1, w+1+n);
	
	int res=0;
	rep(i,1,n){
		if(w[i].w>w[i].id) continue;
		int mx=query(w[i].w-1);
		res=max(res, mx+1);
		upd(w[i].w, mx+1);
	}
	cout<<res<<endl;
	
	return 0;
}