POJ 2373 Dividing the Path DP

线段树转移的完全找不到哪里有问题,然而就是跪弃疗了。抄了份比较短的优先队列。。。。

感觉网上都是铺天盖地的单调队列,这个优先队列也真是玄学。感觉不太容易想到。

对了!这种从0开始的出题人!就应该****!=.=

f[i]表示[0,i]被刚好覆盖的最小代价。注意是刚好覆盖,别出头。[……]

Read more

POJ 1390 Blocks DP

最开始以为这道题是简单的区间DP。我的想法是每次尝试删两边相同的,或者把区间一分为2。但是这个想法存在,问题,一旦一段序列,两段一个色。中间还有一段跟两段一个色,那么久可能存在一种最优解,是删掉3处颜色相同的间隔部分,然后统一删除掉这3个。当然也存在中间有多个和两段相同的情况。所以这么做是不对的。[……]

Read more

POJ 1037 A decorative fence DP

这题挺复杂的。

设dp[i][k][0/1]表示 i个木棍,第k小在第一个,为波峰型/波谷型的方案数。

这个转移倒十分显然。

dp[i][k][0] = sum(dp[i – 1][k -> i][1])

dp[i][k][1] = sum(dp[i – 1][1 -&[……]

Read more

bzoj 3876: [Ahoi2014]支线剧情 上下界费用流

上下界费用流裸题。

神犇题解传送门http://blog.csdn.net/popoqqq/article/details/43024221

跑spfa的时候没判边是否有流量,真是zz。。。

bzoj 1093: [ZJOI2007]最大半连通子图 强联通分量 拓扑排序 DP

这题很容易看出来做法,实现起来也很简单。

首先我们考虑,他这个半联通子图这个概念非常不好处理,我们尝试把他转化一下。想一下,为了求一个最大的半联通子图,显然在一个强联通分量内,我们应该是依次经过某些点,走出一条路径,然后延伸到强联通分量外的路径上。这样子我们可以先求强联通分量,然后在新图上进行[……]

Read more

bzoj 4873: [Shoi2017]寿司餐厅 网络流 最大闭合子权图

这题考场上看出来是网络流了,也看出来是最大闭合子权图了,然后建图有一些差错,dinic 神TMD细节写错一直死循环……….然后GG。。

建图还是比较显然的。我们考虑对于每一个区间[i,j]连向[i+1,j] 和[i,j – 1]。如果i == j 就连向寿司i。然后每个寿司连向对应[……]

Read more

省选模板-数据结构-带权并查集

省选模板-数据结构-并查集

省选模板-数据结构-pb_ds可并堆

省选模板-数据结构-splay平衡树

该伸展的地方别忘记伸展,加入操作切忌不要写成 if (v) ch[v][dir] = ++tot 可能造成tot没加的情况。