一个比较好写的 dp + 线段树优化或树状数组优化即可，绿差不多。