区间 DP 的新经典套路。 Description BX 正在进行一个字符串游戏,他手上有一个字符串 $L$,以及其他一些字符串的集合 $S$,然后他可以进行以下操作:对于一个在集合 $S$ 中的字符串 $p$,如果 $p$ 在 $...
区间DP
洛谷 P4170 [CQOI2007]涂色 题解【区间DP】【贪心】
区间特性很容易看出来,但是DP就不一定了。。。 题目描述 假设你有一条长度为5的木版,初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度...
POJ 1179 [IOI1998]Polygon 题解【区间DP】
正常的拆环为链的环形->区间DP。 Description Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1, where N=4. Each vertex...
洛谷 P1040 NOIp2003提高组 加分二叉树 题解【区间DP】【树的遍历】
树的中序遍历实则就表示了一棵子树的形态。 题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记...
bzoj 1910 [CTSC2002] Award 颁奖典礼 题解【DP】【前缀和】
清奇的前缀和优化。 Description IOI2002的颁奖典礼将在YONG-IN Hall隆重举行。人们在经历了充满梦幻的世界杯之后变得更加富于情趣。为了使颁奖典礼更具魅力,有人建议在YONG-IN Hal...
洛谷 P3205 [HNOI2010]合唱队 题解【区间DP】【分类讨论】
区间DP+分类讨论 题目描述 为了在即将到来的晚会上有更好的演出效果,作为AAA合唱队负责人的小A需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共N个人,第i个人的身高为...
洛谷 P1436 棋盘分割 题解【搜索】/【区间DP】【前缀和】
为什么正解是DP。。。 题目描述 将一个8×8的棋盘进行如下分割:将原棋盘割下一块矩形棋盘并使剩下部分也是矩形,再将剩下的两部分中的任意一块继续如此分割,这样割了(n-1)次后,...
洛谷 P2145 [JSOI2007]祖码 题解【DP】【区间DP】
一个比较有技巧的区间DP题,要缩点,将相同颜色的点整理到一起。 题目描述 这是一个流行在Jsoi的游戏,名称为祖玛。精致细腻的背景,外加神秘的印加音乐衬托,彷佛置身在古老的国度...