こちらも典型かな。
https://yukicoder.me/problems/no/777
問題
N個のケーキがある。
それぞれ奥行A[i]、幅B[i]、カロリーC[i]である。
このうちいくつかのケーキを任意の順で重ねることを考える。
ただし、上のケーキは下より奥行き・幅ともに小さくなければならない。
ケーキの積み重ね方のうち、カロリーの総和の最大値を求めよ。
解法
RMQで解く。
幅を座標圧縮しておき、SegTreeでKeyに幅、Valueにカロリー総和を持ち、区間内の最大値を求められるようにしておく。
あとはケーキを奥行き順降順にソートし、処理する。
自身の幅より大きなKeyの区間のうち、Valueの最大値の物を求めよう。
得られたケーキの上に、自身を乗せると考え、RMQのデータを更新していく。
int N; template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=0; V comp(V l,V r){ return max(l,r);}; SegTree_1(){val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y if(r<=x || y<=l) return def; if(x<=l && r<=y) return val[k]; return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)); } void update(int entry, V v) { entry += NV; val[entry]=comp(v,val[entry]); while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; SegTree_1<ll,1<<20> st; vector<vector<int>> E; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; vector<int> B; B.push_back(0); FOR(i,N) { cin>>x>>y>>r; E.push_back({-x,y,r}); B.push_back(y); } sort(ALL(B)); B.erase(unique(ALL(B)),B.end()); sort(ALL(E)); ll ma=0; FORR(e,E) { y=lower_bound(ALL(B),e[1])-B.begin(); ll a=st.getval(y+1,1<<19)+e[2]; st.update(y,a); ma=max(ma,a); } cout<<ma<<endl; }
まとめ
776の前にこっちでもよかったかもね。