题目描述
Bessie 有一行
Bessie 想要最小化瓷砖的总丑陋度,其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和;即
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
Bessie 有一行
Bessie 想要最小化瓷砖的总丑陋度,其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和;即
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
题目链接:P2106 Sam 数 - 洛谷。
本题是经典矩阵乘法优化 DP 题目。
小 Z 最近发现了一种非常有趣的数,他将这种数称之为 Sam 数。
Sam 数具有以下特征:相邻两位的数字之差不超过
题目链接:P2703 [NOI2006] 千年虫 - 洛谷。
本题使用奇妙性质优化 DP。
千年虫是远古时代的生物,时隔几千万年,千年虫早已从地球上销声匿迹,人们对其知之甚少。考古生物学家最近开始对其有了兴趣,因为一批珍贵的千年虫化石被发现,这些化石保留了千年虫近乎完整的形态。
理论科学家们根据这些化石归纳出了千年虫的一般形态特征模型,并且据此判定出千年虫就是蜈蚣的祖先!但科学家 J 发现了实际与理论的一些出入,他仔细的研究了上百个千年虫化石,发现其中大部分千年虫的形态都不完全符合理论模型,这到底是什么因素造成的呢?理论科学家 K 敏锐的指出,千年虫的形态保存在化石中很有可能发生各种变化,即便最细微的变化也能导致它不符合模型。
题目链接:P2470 [SCOI2007] 压缩 - 洛谷。
给一个由小写字母组成的字符串,我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小写字母外还可以(但不必)包含大写字母 R 与 M,其中 M 标记重复串的开始,R 重复从上一个 M(如果当前位置左边没有 M,则从串的开始算起)开始的解压结果(称为缓冲串)。
bcdcdcdcd
可以压缩为 bMcdRR
,下面是解压缩的过程:
已经解压的部分 | 解压结果 | 缓冲串 |
---|---|---|
b | b | b |
bM | b | . |
bMc | bc | c |
bMcd | bcd | cd |
bMcdR | bcdcd | cdcd |
bMcdRR | bcdcdcdcd | cdcdcdcd |
题目链接:P2145 [JSOI2007] 祖玛 - 洛谷。
这是一个流行在 Jsoi 的游戏,名称为祖玛。
精致细腻的背景,外加神秘的印加音乐衬托,彷佛置身在古老的国度里面,进行一个神秘的游戏——这就是著名的祖玛游戏。祖玛游戏的主角是一只石青蛙,石青蛙会吐出各种颜色的珠子,珠子造型美丽,并且有着神秘的色彩。
环绕着石青蛙的是载着珠子的轨道,各种颜色的珠子会沿着轨道往前滑动,石青蛙必需遏止珠子们滚进去轨道终点的洞里头,如何减少珠子呢?就得要靠石青蛙吐出的珠子与轨道上的珠子相结合,颜色相同者即可以消失得分!直到轨道上的珠子通通都被清干净为止。 或许你并不了解祖玛游戏。没关系。这里我们介绍一个简单版本的祖玛游戏规则。一条通道中有一些玻璃珠,每个珠子有各自的颜色,如图 1 所示。玩家可以做的是选择一种颜色的珠子(注意:颜色可以任选,这与真实游戏是不同的)射入某个位置。
给定
矩阵乘法并不满足交换律,但是其满足结合律,因此我们可以通过合理安排结合顺序,尽可能减少需要的运算次数。在此题中,我们定义将一个大小为
请你算出将题目所给的
题目链接:P1912 [NOI2009] 诗人小G - 洛谷。
本题是 DP 四边形不等式优化经典题型。
小 G 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。
一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的
题目链接:P1081 [NOIP 2012 提高组] 开车旅行 - 洛谷。
小
旅行过程中,小
小
题目链接:P3571 [POI 2014] SUP-Supercomputer - 洛谷。
本题是经典斜率优化题型。
Byteasar has designed a supercomputer of novel architecture.
1 |
|