Browse Category

区间DP

ECNU 3355 开心消消乐 (dp)

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

POJ 3280 Cheapest Palindrome (区间DP)

给出一个由n种字母组成的长度为m的串,然后给出这n种字母的添加和删除的代价,问如何使用最小的代价通过添加字母与删除字母使得原串变成回文串。

HDU 2476:String painter (区间DP)

给出两个字符串,每次我们可以把一个字符串的一个区间刷成同一个字母,问最少多少步可以把第一个字符串变为第二个字符串