BZOJ3437 小P的牧场 && SDOI2016 征途  斜率优化 动态规划

BZOJ3437 小P的牧场 && SDOI2016 征途 斜率优化

BZOJ3437: 小P的牧场 这题思路十分清奇,我一开始推了个正常的DP式子,大力化简,发现无论如何也化不出来斜率优化的形式,去看了题解才知道是要逆向思维:因为每个控制站都只能控制当前点和左边的点,所以n号点一定要放。因此可以设f[i]为在n-1~i中新增控制点i所能节省的最大费用,f[i]=ma···
[USACO Mar08]土地购买  斜率优化 动态规划

[USACO Mar08]土地购买 斜率优化

观察发现,若矩形A的长宽均大于矩形B,则选中矩形B不需要花费额外费用。 所以先进行二元组排序,维护一个单调栈,保证在x单调增的同时y单调减(类似样例的形式)。 而后,选择的矩形即为连续的区间,所以搞成了一个线性DP。 设f[i]:到i为止组成新块的最小花费,则f[i]=min{f[j]+x[i]*y···