Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


  1. 「SHOI2008」仙人掌图 - 仙人掌 DP

    求仙人掌图的直径。

    于  BZOJ, DP, SHOI, Tarjan, 仙人掌 继续阅读

  2. 「IOI2008」岛屿 - 基环树 DP

    给一个由多个基环树构成的图,求所有基环树最长链之和。

    于  BZOJ, DP, SHOI, Tarjan, 基环树 继续阅读

  3. 「NOIP2015」子串 - DP

    有两个仅包含小写英文字母的字符串 A A B B 。现在要从字符串 A A 中取出 k k 个互不重叠的非空子串,然后把这 k k 个子串按照其在字符串 A A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B B 相等?
    注意:子串取出的位置不同也认为是不同的方案。

    于  CodeVS, DP, NOIP 继续阅读

  4. 「SHOI2008」循环的债务 - DP

    A、B、C 三个人之间互相有一些债务,每个人有每种面值 1,5,10,20,50,100 1, 5, 10, 20, 50, 100 的钞票若干,求使他们把债务还清的最少交换的现金数量。

    于  BZOJ, DP, SHOI 继续阅读

  5. 「SHOI2008」汉诺塔 - DP

    在任何操作执行之前,我们以任意的次序为六种操作(AB、AC、BA、BC、CA 和 CB)赋予不同的优先级,然后,我们总是选择符合以下两个条件的操作来移动盘子,直到所有的盘子都从柱子 A 移动到另一根柱子:

    1. 这种操作是所有合法操作中优先级最高的;
    2. 这种操作所要移动的盘子不是上一次操作所移动的那个盘子。

    可以证明,上述策略一定能完成汉诺塔游戏。
    现在你的任务就是假设给定了每种操作的优先级,计算按照上述策略操作汉诺塔移动所需要的步骤数。

    于  BZOJ, DP, SHOI 继续阅读

  6. 「NOIP2014」飞扬的小鸟 - 背包 DP

    • 游戏界面是一个长为 n n ,高为 m m 的二维平面,其中有 k k 个管道(忽略管道的宽度)。
    • 小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。
    • 小鸟每个单位时间沿横坐标方向右移的距离为 1 1 ,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 X X ,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 Y Y 。小鸟位于横坐标方向不同位置时,上升的高度 X X 和下降的高度 Y Y 可能互不相同。
    • 小鸟高度等于 0 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m m 时,无法再上升。

    现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

    于  COGS, CodeVS, DP, NOIP, 背包 DP 继续阅读

  7. 「ZJOI2004」沼泽鳄鱼 - 矩阵乘法

    给一个图,有一些鳄鱼在两个、三个或四个点之间周期性移动,求从 s s 点到 t t 点,恰好走 k k 步,任意时刻都不与鳄鱼同时到达同一个点的方案数。

    于  BZOJ, COGS, DP, ZJOI, 矩阵乘法 继续阅读

  8. 「HNOI2008」GT考试 - KMP + 矩阵乘法

    给一个长度为 m m 的字符串 T T ,求长度为 n n 且不包含 T T 的字符串的数量。

    于  BZOJ, DP, HNOI, KMP, 字符串, 快速幂, 矩阵乘法 继续阅读

  9. 「BZOJ 2580」Video Game - AC 自动机

    给出 n n 个串 si s_i ,求一个长度为 k k 的串 S S ,使 S S 匹配 si s_i (可重叠)的次数最多。

    于  AC 自动机, BZOJ, DP, USACO, 字符串 继续阅读

  10. 「JSOI2007」文本生成器 - AC 自动机

    「文本生成器」可以随机生成一些文章 ―― 总是生成一篇长度固定且完全随机的文章 —— 也就是说,生成的文章中每个字节都是完全随机的。

    如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章 a a 包含单词 b b ,当且仅当单词 b b 是文章 a a 的子串)。

    求生成的所有文本中可读文本的数量。

    于  AC 自动机, BZOJ, DP, JSOI, 字符串 继续阅读