Description

有(k)个点，试选出一些点，满足(forall{j}<i,x_j<x_i,y_j<y_i)，且最大化(sum{z_i})

Solution

和(P2344)很像呀。

首先将坐标离散化并按(x[i])排序后，可以写出(dp)方程：(dp[i]=sumlimits_{j=1}^{i-1}max{dp[j]}+z[i](y[j]le{y[i]}))。

但是这样做是(O(k^2))的。考虑如何优化。

其实也是一个二维数点。而(i,j)是天然有序的，我们可以把(y_i)作为树状数组下标，再把(dp_i)依次加到树状数组里，算出答案就可以了。注意树状数组维护的是(max)，然后答案为(max{dp_i})。