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)当点的横坐标不单调且直线斜率不单调的时候。如果用单调队列,那么求最优决策点还是可以二分。当插入一个点的时候,我们首先根据它的横坐标二分出它的插入位置,然后维护凸壳,但是由于可能插入在队列中间,两边都要删点,复杂度过高。
正确做法是用平衡树维护动态凸壳。(我擦,说着简单,写着蛋疼无比)(这种情况细节还不太会,有待学习)

poj3017 Cut the Sequence

单调队列+treap
会爆栈,要c++扩栈。
题意:给出n个数(n<=10^5),给出m,要求将数列分成连续的若干段,使得每段之和<=m,且每段中的最大值的和最小,求这个最小的和
分析:
很容易得到:dp[i]=min{dp[j]+max{a[j+1……i]}|bound[i]<=j<=i-1},其中bound[i]是使得sigma(a[j+1]……a[i])<=m的最大下标,可以二分得到。
状态数O(n),转移O(n),显然要优化。
由于bound[i]是随着i的增大单调不降的,而且一个点j要成为i的最优决策首先必须满足a[j]比a[j+1……i]都要大(这点还不明白)。那么我们可以用单调队列维护。
现在对于确定的决策j,我们可以O(1)时间知道a[j+1]~a[i]的最大值(若q[p]=a[j],那么max{a[j+1]~a[i]}=q[p+1],q[p+1]存在的前提下),但是对于状态i,当前单调队列的队首元素的原始下标不一定就是最优决策值,所以我们要找到一种数据结构动态的维护dp[j]+max{a[j+1]~a[i]},其中a[j]是当前单调队列中的元素。那么显然当状态转移的时候需要对这种数据结构插入、删除、求最小值。显然这种数据结构应当是平衡树为好。
思路还是很清晰的,但是要注意细节,队列中的元素个数要时刻清晰,插入删除了哪些决策下的答案要清楚。还有就是对于决策是bound这种情况,要特判。因为我代码里面的单调队列都是从bound+1开始的元素。

上下界网络流的一些理解

周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧,转变成无源汇可行流问题
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉。从s到t求最大流,(网上说要去掉附加源汇ss,tt,其实我感觉不用去,因为ss和tt间没边,所以必要弧不可能退流,个人理解,正确性有待检验)
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加,求ss到tt的最大流ans2
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且的流量就是最小流,否则无解
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0