道路染色

　　题意：一棵树，给边染色，要求相邻边颜色不相同，染不同的颜色代价不同，求最小代价方案。n<=150

　　考虑在树上DP，如果确定了一棵子树根上边那条边的颜色，整个子树的最小代价就能确定。所以F[i][j]表示以i为根的子树，根上面的边颜色是j时，整个子树+j的总代价。

　　考虑状态转移。这题最重要的地方就是状态转移的时候是一个经典的二分图最优匹配模型。所以用KM转移状态即可。

几乎平均数

　　定义Σ/(len-1)为几乎平均数，求一段区间内最大的的几乎平均数。

　　方法一：考虑部分枚举。枚举起点后发现我们需要一个数据结构维护一个比例式的最大值，同时支持插入和删除。所以是动态凸包。

　　方法二：还可以考虑用空间换时间。枚举起点和终点，可以更新其对应的区间。为了减少重复运算，所以倒过来更新，f[i][j]=max{f[i-1][j],ans(i,j),f[i][j-1]}

　　以上两种方法各有利弊，考虑综合一下。

　　对空间分块。因为方法二太费内存，所以在空间上分块搞，每块内部用方法一，块之间用方法二。

和与积

　　暴力20分。

　　考虑利用gcd。一顿乱搞40分？

　　ayq的题解里讲的挺明白了。这题比赛时也就有暴力的份吧。。

wsc500原创，转载请注明出处。请注明 出自http://www.cnblogs.com/loveidea/