分类 区间DP 下的文章

BZOJ 1652: [Usaco2006 Feb]Treats for the Cows

Description约翰经常给产奶量高的奶牛发特殊津贴,于是很快奶牛们拥有了大笔不知该怎么花的钱.为此,约翰购置了N(1≤N≤2000)份美味的零食来卖给奶牛们.每天约翰售出一份零食.当然约翰希望这些零食全部售出后能得到最大的收益.这些零食有以下这些有趣的特性:• 零食按照1..N编号,它们被排成一列放在一个很长的盒子里.盒子的两端都有开口,约翰每天可以从盒子的任一端取出最外面的一个.•与美酒与好吃的奶酪相似,这些零食储存得越久就越好吃.当然,这样约翰就可以把它们卖出更高的价钱.•每份零食的初始价值不一定相同.约翰进货时,第i份零食的初始价值为Vi(1≤Vi≤1000).- 阅读剩余部分 -

BZOJ 1068: [SCOI2007]压缩

题目描述给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母R与M,其中M标记重复串的开始,R重复从上一个M(如果当前位置左边没有M,则从串的开始算起)开始的解压结果(称为缓冲串)。 bcdcdcdcd可以压缩为bMcdRR,下面是解压缩的过程另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。输入输入仅一行,包含待压缩字符串,仅包含小写字母,长度为n。输出输出仅一行,即压缩后字符串的最短长度。样例输入bcdcdcdcdxcdcdcdcd样例输出12提示在第一个- 阅读剩余部分 -

洛谷 P1040 加分二叉树

题目描述设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:subtree的左子树的加分× subtree的右子树的加分+subtree的根的分数。若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。要求输出;(1)tree的最高加分(2)tree的前序遍历输入- 阅读剩余部分 -