#Apio2014

UOJ#104. 【APIO2014】Split the sequence 动态规划 斜率优化

原文链接www.cnblogs.com/zhouzhendong/p/UOJ104.html首先证明一个结论:对于一种分割方案,分割的顺序不影响最终结果。证明:对于树a[x]和a[y],如果x与y之间有分割,那么它们对答案的贡献就是a[x]*a[y],否则无贡献。于是问题转化成DP:设dp[i][j]表示把前j个数分成...

UOJ#103. 【APIO2014】Palindromes PAM模板题

原文链接www.cnblogs.com/zhouzhendong/p/UOJ103.html  我终于会PAM啦  感谢CLY大佬手把手教我PAM  建个PAM。  统计一下每一个节点的Right集合大小,设size[x]为节点x的right集合大小。  求出max(len[x]*size[x]),做完了。#inclu...

BZOJ3675 [Apio2014]序列分割 动态规划 斜率优化

原文链接http://www.cnblogs.com/zhouzhendong/p/8697258.html  对于一个非负整数序列,小H需要重复k次以下的步骤:  1.选择一个长度超过1的序列  2.从任意位置将序列分割成两个非空的新序列。  每次,小H将会得到分数。分数为两个新序列中元素和的乘积。请选择一种最佳的分...