1.复杂度 O(n*3^k+cE*2^k)
hdoj3401 Trade
单调队列优化dp,太菜了做不出来啊,看了题解才ok
http://hi.baidu.com/mobius_strip/item/a0152244c47e4ec9c1a592f6
hdoj4122 Alice’s mooncake shop
哎,一道简单的单调队列比赛时候居然没做出来,很不应该。
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
正确做法是用平衡树维护动态凸壳。(我擦,说着简单,写着蛋疼无比)(这种情况细节还不太会,有待学习)
hdoj2993 MAX Average Problem
这篇论文里的例二:http://www.docin.com/p-47950655.html
分析不写了,论文里写的很清楚,虽说不是斜率优化dp,但应该也可以算是斜率优化dp的入门题了。。记得加外挂哦~~
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开始的元素。
hdoj4557 非诚勿扰
居然0ms,数据略水。。
poj1442 Black Box
treap入门题
单调队列
fzoj1894 志愿者选拔
裸的单调队列,注意出队的时候,只有当当前删除的人的下标等于优先队列中队首的人的下标,才出队
钢之炼金术士FA的五首OP
终于看完钢炼FA了,有点不舍,动漫里确实塑造了一个全新的很棒的世界观啊
OP1 again
这首很怀旧
上下界网络流的一些理解
周源论文中的二分法求解虽用途广,但效率不高,容易被卡时间,所以非二分的扩流法和缩流法比较好
注意点:设下界为low,上界为high,残量网络中该边残余容量c,则最后该边的流量=low+(high-low-c)=high-c;亦即上界-残量
1.有源汇上下界最大流
(1)加弧
(2)添加附加源汇ss、tt。求出是否存在可行流。
(3)现在已经有了可行流,去掉
2.有源汇上下界最小流
(1)和最大流一样构造附加网络(但不添加
(2)求ss到tt的最大流ans1
(3)加
(4)如果ans1+ans2等于附加网络的满流流量(以ss、tt为源汇),则有解,且
这个方法无bug,但我还没完全理解
还有一个有bug的方法:和求解最大流基本一样,只是最后一步是从t到s求最大流,也就是缩流,但是存在bug:可能出现缩流的量比可行流还大,也就是最终最小流为负,其实这种情况意味着原网络中间出现环流,也就是源点s不必产生流量也能符合要求,此时最小流为0
上下界网络流专题
各种流的一句话总结,相当经典:http://blog.csdn.net/pouy94/article/details/6628521
zoj 2314 Reactor Cooling
无源汇可行流