[DBOI2019]德里莎世界第一可爱 题解

· · 个人记录

这题是一个很裸的kdtree虽然我并不会打

题目给了四个不等式，我们可以先按其中一维排序，把剩下三维的信息简记为a[] b[] c[]，崩坏兽权值为val[]。令f[0]=0，容易写出dp方程：

f[i]=Max_{j=0}^{i-1}\{f[j]\}+val[i], a[j]<a[i],b[j]<b[i],c[j]<c[i]

这就是一个三维偏序问题了。设计算f[i]，则kdtree中存放i-1个权值为f[j]、坐标为(a[j],b[j],c[j])的点（j<i）。查询(-∞,a[i]) (-∞,b[i]) (-∞,c[i])的长方体中的最大值，这个+val[i]就是等式右边的那一坨的答案了，转移即可。