Browse Category

动态规划

ECNU 3355 开心消消乐 (dp)

大家都玩过一种叫作开心消消乐的游戏。
规则很简单:刚开始有一列不同颜色的方块,每次可以消掉相邻的、颜色相同的若干个($k$ 个),并获得 $k^2$ 分。现在给出一个游戏的起始局面,问最多能获得多少分?

LOJ 6160 二分图染色 (dp,组合数学)

给定一个完全二分图,图的左右两边的顶点数目相同。我们要把图中的每条边染成红色、蓝色、或者绿色,并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。计算所有满足条件的染色的方案数,并对 10^9+7 取模。