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

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

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

a * (b + c) + b * c

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

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

Read more

Noi模拟 最长路径 DP 奇妙推论

【题目描述】

在Byteland一共有n个城市,编号依次为1到n,它们之间计划修建n(n-1)/2条单向道路,对于任意两个不同的点i和j,在它们之间有且仅有一条单向道路,方向要么是i到j,要么是j到i。换句话说,这是一个n个点的竞赛图。

Byteasar居住在1号城市,他希望从1号城市出[……]

Read more

bzoj 4602: [Sdoi2016]齿轮 dfs

找个起始点钦点一个速度,然后搜索,然后矛盾输出即可对吧。好吧,很简单吧。

开始忘记在搜索前钦点速度了,QwQ

bzoj 4562: [Haoi2016]食物链 记忆化搜索

搜就行了,注意单一物种不为食物链。

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 2748: [HAOI2012]音量调节 DP

dp[i][j]表示唱完第i首歌,音量为j是否可行。

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

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

Read more