P3642 [APIO2016] 烟火表演
我不太会证明凸性。
像这道题就是列出 DP 方程，\(f_{u,x}\) 表示以 \(u\) 为根的子树还有 \(x\) 分钟就全爆炸的最小代价。
然后赌它是个凸函数（（
因为它有 \(sum\)，就是两个下凸函数相加，还是下凸的。
然后求前缀的最小值再加一个函数一类的，所以考虑之后这个函数会有什么变化。
我们考虑最低区间为 \([l,r]\)，显然这段的斜率为 \(0\)。
然后考虑这个函数的在合并之后的变化，简单来说就是砍掉斜率大于 \(0\) 的部分，只接上一个斜率等于 \(1\) 的射线。右边虽然要向上平移，但是无所谓的，因为 \(f_0\) 是可以计算的，只需要计算每条线段的斜率就行。然后整个大根堆维护拐点斜率就行。
有一个性质就是每加入一个点就代表之后的斜率减少一。从儿子合并上来的点斜率大于 \(0\) 的点只有儿子个数个。所以在当前点找 \(l\sim r\) 就弹掉儿子个数个点就行。
P2605 [ZJOI2010]基站选址
朴素 DP 还挺简单的。
然后就是考虑区间里怎样求不能被覆盖的基站。
就是把所有村子的最远可行距离求出来，记为 \(st_i,ed_i\)，然后挂在 \(ed_i\) 上，求完 \(f_i\) 之后就把 \(1\sim st_{k}-1\) 都加上 \(w_k\) 就行。(\(k\) 是挂在 \(i\) 上的点)
废话
是这样的，本来我还想写点东西，但是想先撸猫。但是我妈催我去写题，这样我就完全不想写东西了。现在除了撸猫什么都不想干。
撸猫去。
撸猫是最重要的正事，学它喵的什么习，哪有撸猫重要。
喵呜呜喵喵喵呜喵
标签：4.11,Set,凸函数,Solution,然后,斜率,就行 From： https://www.cnblogs.com/cc0000/p/17307960.html