bzoj 3675: [Apio2014]序列分割 斜率优化

首先你要发现这题有个奇妙的性质,就是说当你一个切割方案确定下来,你切的先后的顺序对最终的答案没有任何影响。

做一个简单的证明,假设a b c我们考虑先切a右侧,再切b右侧答案是

a * (b + c) + b * c

先切b右侧,再切a右侧,答案是

(a + b) * c +[……]

Read more

bzoj 3238: [Ahoi2013]差异 后缀数组 单调栈

很详细:http://blog.csdn.net/wzq_qwq/article/details/48215019

bzoj 4518: [Sdoi2016]征途 DP 斜率优化

原式可以化简成  m * sum(xi^2)(i = 1 – > m) – sum(xi)(i = 1 -> m)

如果你很好奇为什么可以化成这个形式,请注意一个事实。x的平均值*m是等于所有的和。

我们发现我们无非就是求最小的sum(xi^2)(i = 1 -> m)[……]

Read more

bzoj 1875: [SDOI2009]HH去散步 矩阵乘法优化

这题要求不能走一条边然后立即走回来。所以用点来进行dp不太好判断,我们考虑用边进行DP。dp[i][j]表示走完第i条边总距离为j的方案数。所有边拆成2条,然后用矩阵优化下转移就好了。注意矩阵不要搞太大,刚好就好,否则容易RE爆栈。开始在处理不能从自己的反向边走来的地方处理的不太好,然后GG。
[[……]

Read more

bzoj 4198: [Noi2015]荷马史诗 优先队列 哈夫曼编码

大概颓了两天之后心情好了点。QwQ。写了一发题。。

讲道理喝维他柠檬茶来消愁,感觉,好贵,冰红茶只有一半价格的说。。233

大概哈夫曼编码随便搞一下就好了,很简单。

2进制的哈夫曼是二叉树,那你就k叉树好了。

唯一注意一下的就是,常见的二进制喊夫曼树是你有多少个元素都可以把树[……]

Read more

bzoj 1067: [SCOI2007]降雨量 线段树 离散化

这种题都是一眼就能看出做法,然后细节太多半天写不出来。从上午写到下午,最后参考了别人的代码,才写完的。quq,还是自己太水了。

离散化后可能导致线段树去查(l + 1,r – 1)的时候会查出未知的东西,中间应该插点间隔。

bzoj 1855: [Scoi2010]股票交易 DP

最开始各种YY网络流。

然后发现很不可做的样子。

然后开始YYDP。

然后发现DP[i][j]表示前i天手存j个股票的最大收益。

然后一看n^2DP,妙啊~~

八中少有的水题。

后来发现转移还有1维。。。。

然后查了题解,说是可以单调队列优化。第一次写,写的[……]

Read more

bzoj 2301: [HAOI2011]Problem b 莫比乌斯反演

原来bzoj用cout真的会RE。。。。。。真是涨见识了。。。。。。