uva12589 Learning Vector

比赛的时候没想到是背包的dp啊。。。
思路:先按斜率排序,因为对于确定的一些向量,一定是斜率大的在前可以使总面积最大化。dp方程主体是背包,但是加了一维,表示最右侧的向量的最高点的y值。也就是dp[i][j][k]表示前i个向量中选取j个且最右侧高为k的最大面积。可以用滚动数组省掉阶段那一维,然后和一般背包不同的是,因为如果填表的话,每次对于dp[i][j][k],都要枚举dp[i-1][j-1][0……k-1],复杂度很高,所以用刷表的方式,每次用dp[i][j][k]更新dp[i+1][j+1][k+p[i].y]。

hdoj3698 Let the light guide us——线段树优化dp

终于ac了,好久不写线段树,成段更新变生疏了。
第一道用线段树优化的dp题。线段树用于成段更新,求区间最小值(包括历史值在内的最小值)。
dp[i][j]:前i行,且第i行选第j个可以得到的最小花费
dp[i][j]=min{dp[i-1][k]|1<=k<=m且abs(j-k)<=f[i-1][k]+f[i][j]}+cost[i][j]
复杂度n*m*m,超时
其实对于确定的i,j可以选择哪些k呢?abs(j-k)<=f[i][j]+f[i-1][k]等价于以j为中心,f[i][j]为半径的区间和以k为中心,f[i-1][k]为半径的区间的重合部分,so。。求解每个阶段的时候,可以建立线段树[1,m],然后不断加入上个阶段的dp值,dp[i-1][k]的区间是
[max(1,k-f[i-1][k]),min(m,k+f[i-1][k])],线段树维护最小值,注意lazy字段,lazy表示要往下更新的最小值,但是子孙节点的lazy有可能是小于它的(加入先对父区间更新为10,然后左子区间更新为8,这时候子区间的lazy就要比父区间小了),所以pushdown的时候,只有儿子节点的lazy没值或者小于父节点的lazy,才能重写这个儿子节点的lazy,否则可能导致结果偏大

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开始的元素。

hdoj4705–2013多校第10场Y题

树形dp:
dp[i]表示结点i为根的子树中无法形成简单路径的点对数。有如下几种情况:
(1)对于以点i为根的子树,两个点在i的一颗子树中(不成祖先后代关系),还有一个点在i的另一棵子树中。
(2)3个点分散在i的三棵子树中(i存在三个儿子的情况下)
比赛的时候很快就想到了这个,思路很简单,但是在想细节的时候,发现对于第二种情况是3次方枚举,然后队友说这题差不多了,我就没再想,去看其他题了,交给队友敲。后来发现队友TLE了,才知道他也是三次方的枚举。。。这,早点交流其实可以避免。。三次方必然超时嘛。。
然后俩队友讨论出了线性时间的方法,后来我又回来看这题(==这场的网络流好难。。),听队友讲了线性时间解决方法,似懂非懂。于是决定自己推。。推出来和队友的还是有些不一样的。。多算了些东东,多减了些东东
本质:对于n个数,a1~an,O(n)时间求其中下标不重复的三个数的积的总和(组合而非排列:a1*a2*a3和a2*a3*a1是一样的)。
设s=a1+a2+……+an,c=a1^2+a2^2+……+an^2所求答案为ans
在稿纸上算一下:ans=(s^3-[a1*(c-a1^2)+a2*(c-a2^2)+……+an*(c-an^2)]+[a1^2*(s-a1)+a2^2*(s-a2)+……+an^2*(s-an)]+s*c)/6;
仔细打下草稿还是可以出来的,最后除以3!是因为三个数进行了全排列。

hdoj4628——2013多校第三场Pieces

题意:给定一个长度不超16的字符串,每次可以去掉一个回文序列(序列亦即可以不连续,但要顺序不变),问最少几次可以使原字符串为空?
思路:状压dp,(比赛时队友用bfs也过了,貌似速度比状压还要快。。)dp[i]表示到达i状态所需的最小步数。
先预处理出所有状态是否是回文序列。然后dp更新的时候有两种方法:一种是访问到i,用比它大的状态更新它,即填表,一种是访问到i,则更新所有它的子状态,即刷表。但是无论哪种,在更新时都要用到一个奇技淫巧:假如j是i的子状态(i为0的位,j必为0),那么i&(j-1)就表示比j小一点的i的子状态。因为i&sth保证了是i的子状态,(j-1)&sth保证了这个状态比j小一点。这个技巧减少了许多无用状态。效率大幅提高。
复杂度分析:对于每个状态,都要枚举他的子状态:c(n,n)*2^n+c(n,n-1)*2^(n-1)+……+c(n,1)*2^1+c(n,0)*2^0=(2+1)^n=3^n
代码:
填表

树形dp专题(更新ing)

前段时间做线段树,结果做不下去了。。感觉dp太弱,遂打算做个专题,tree dp之后是状压,往后是数位dp和概率dp,不过图论也要抓起来
几个链接:
背包九讲:http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
论文《几类背包问题》:http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html
依赖背包博文:http://www.cnblogs.com/GXZC/archive/2013/01/13/2858649.html
zero clock背包总结:http://blog.csdn.net/woshi250hua/article/details/7636866
开个树形dp专题:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25888#overview
(一)一般树形dp
(二)树形dp+分组背包
因为有分支,所以树上的背包要容量要分配,但是因为是依赖背包,所以根一定要选。从根往下看是分配,代码中实际是从叶子往上合并的,这种合并其实就是dd神牛的背包九讲里面的泛化物品,实质是把对一棵子树的决策(分配多少容量给该子树,因为决策互斥)作为一件物品,这样,合并=实际上就是做一次分组背包,一棵子树就是一个组,每组物品有dp[son][0]~dp[son][V-w[fa]]。为什么是V-w[fa]呢,因为父节点时一定要选的,所以给子节点的容量最多也就V-w[fa]。
////////////////////////////////////
hdoj1561
典型的依赖背包,因为可能是深林,所以以0为虚拟根,val[0]=0,w[0]=1;