kmjp's blog

競技プログラミング参加記です

yukicoder : No.777 再帰的ケーキ

こちらも典型かな。
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の前にこっちでもよかったかもね。