D - Flat Subsequence Editorial by Mitsubachi
ここで、 $A_i$ を使う場合と使わない場合で分けて考えることで遷移は
また、答えは $\max(dp[N][0],dp[N][1], \cdots ,dp[N][300000])$ です。しかし、これを愚直に書くと $O(NK)$ となってしまい、間に合いません。
dp配列を使いまわすと、 $1$ つめの遷移は行わなくてもよいことが分かります。
そこで $2$ つめの遷移を考えます。これには区間の最大値の取得、配列の $1$ 点を更新する処理が必要です。
これらの処理は Range Max Query と呼ばれるもので、 segment tree を用いて処理することができます。
C++の場合、atcoder/all もしくは atcoder/segtree を include することで使える ACLの segtree
を用いると容易に実装できます。
頂点にその頂点が対応する区間に対するクエリの答えを用意することで、区間の一点更新、区間に対するクエリの答えの取得を $O(\log N)$ で行えます。詳しくは下の記事をお読みください。
参考記事
実装例(C++)
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
//op : segment tree の2要素に対する演算
//sのl番目からr番目までの区間に対する求めたいものは op(s_l,op(s_{l+1},...,s_r)) にあたる
//今回は max(s_l,max(s_{l+1},...,s_r)) にあたるので op は max にあたるものを書く
int op(int a,int b){
return max(a,b);
}
//e : 単位元
//op(a,e) = aとなる
int e(){
return 0;
}
int main(){
int n,k;
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
//300001要素のsegtree(Range Max Query)を作る
//seg[i]でiが末尾のBで長さが最長のものの長さ
segtree<int,op,e> seg(300001);
for(int x:a){
//区間の左端,右端がl,r(負になったり300001より大きくなったりしないようにmaxやminで調整)
int l=max(x-k,0),r=min(x+k+1,300001);
//prodで区間に対する最大値を取得
//prod(a,b)でa番目から"b-1"番目までなので注意(b番目は含まない)
int mx=seg.prod(l,r);
//seg[x]の更新
seg.set(x,mx+1);
}
//全要素の最大値を取得
int ans=seg.all_prod();
cout<<ans<<endl;
}
posted:
last update: