hdoj3507 Print Article

比较水的斜率优化dp
dp[i]:前i个词的最小cost
s[i]:前i个词的cost之和
w[j,i]:把第j到i个词分在一行的cost
dp[i]=min{dp[j]+w[j+1,i]}(0<=j<=i-1)
其中w[j,i]=(s[i]-s[j])^2+m
dp[i]的是式子展开:dp[i]=min{dp[j]+s[j]^2-2s[i]*s[j]}+s[i]^2+m
k=2s[i]
x=s[j]
y=dp[j]+s[j]^2
点的横坐标非递减,所以可以用单调队列维护凸壳,因为斜率非递减(即决策单调),所以可以均摊O(1)的求出最优决策是哪个,总复杂度O(n)
//////////////////
关于决策单调的另一种严格证明:
即证明w[i,j]满足四边形不等式:对于i<i’<j’<j,w[i,j']+w[i',j]<=w[i,j]+w[i',j']
(s[j']-s[i])^2+(s[j]-s[i'])^2<=(s[j]-s[i])^2+(s[j']-s[i'])^2
继续化简:-2s[i]s[j']-2s[i']s[j]<=-2s[i]s[j]-2s[i']s[j']
s[i]s[j']+s[i']s[j]>=s[i]s[j]+s[i']s[j']
(s[i']-s[i])(s[j]-s[j'])>=0
因为i<i’<j’<j,(s[i']-s[i])(s[j]-s[j'])>=0显然成立,所以w[i,j]满足四边形不等式,决策单调

hdoj2829 Lawrence

我擦。。去掉一个语句居然就ac了,纠结n久。这题貌似不用斜率有优化,用四边形不等式优化也行。具体明天再说。。
第一道状态是二维,决策一维的斜率优化dp,其实和状态一维的差不多,无非多了层外层循环。每个阶段都用一下单调队列。。

bzoj1010 玩具装箱toy

斜率优化dp第一题,纠结了n久。。最后输出改成%I64d就PE,要%lld才能ac,而且把输入也改成%lld比%I64d快看了200MS。。
终于大致清楚了斜率优化dp,记下几点:
(1)求最大值,维护上凸壳;求最小值,维护下凸壳;
(2)当点的横坐标单调,且斜率单调时,此时决策是单调的(即满足四边形不等式),可以用单调队列从前往后找最优决策(怎么找?只有最优决策点的值比两侧都要优,注意只有二字),找到之后前面的都是无用决策了,插入点的时候维护队列凸壳。
(3)如果点的横坐标是单调的,而斜率不单调,这时候决策是不单调的,但是可以发现最优决策点与两侧相邻点的斜率分别是k1,k2(k1 那么显然此时直线簇的斜率k满足k1 (4)当点的横坐标不单调且直线斜率不单调的时候。如果用单调队列,那么求最优决策点还是可以二分。当插入一个点的时候,我们首先根据它的横坐标二分出它的插入位置,然后维护凸壳,但是由于可能插入在队列中间,两边都要删点,复杂度过高。
正确做法是用平衡树维护动态凸壳。(我擦,说着简单,写着蛋疼无比)(这种情况细节还不太会,有待学习)