Menci

眉眼如初,岁月如故

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


  1. 「Codeforces 808G」Anthem of Berland - KMP + DP

    给一个含有字母以及 ?s s 串和一个含有字母的 t t 串,其中 ? 可以匹配任何字符,求 s s 串最多匹配 t t 串多少次。

    于  Codeforces, DP, KMP, 字符串 继续阅读

  2. 「APIO2014」Split the sequence - 斜率优化 DP

    你正在玩一个关于长度为 n n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1 k + 1 个非空的块。为了得到 k+1 k + 1 块,你需要重复下面的操作 k k 次:

    1. 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
    2. 选择两个相邻元素把这个块从中间分开,得到两个非空的块。

    每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

    于  APIO, BZOJ, DP, UOJ 继续阅读

  3. 「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

    给出 m m 个串组成的「标准作文库」。对于任意一个串,如果它的长度不少于 L L 且在标准作文库中出现过,则它是「熟悉」的。对于任意一个串,如果能将它划分为若干个串,使「熟悉」的串的长度超过总长度的 90% 90\% ,则称这个串是「熟悉的文章」,定义 L0 L_0 为使这个串成为「熟悉的文章」的最大的 L L 。给出若干个串,求每个串的 L L 值。

    于  BZOJ, CTSC, DP, SAM, 二分, 单调队列, 字符串 继续阅读

  4. 「BZOJ 1677」求和 - DP

    给出一个 N N ,使用一些 2 2 的若干次幂的数相加来求之。问有多少种方法。

    于  BZOJ, DP, USACO, 背包 DP 继续阅读

  5. 「TJOI2015」组合数学 - DP + 结论

    给出一个网格图,其中某些格子有财宝,每次从左上角出发,只能向下或右走。问至少走多少次才能将财宝捡完。此对此问题变形,假设每个格子中有好多财宝,而每一次经过一个格子至多只能捡走一块财宝,至少走多少次才能把财宝全部捡完。

    于  BZOJ, DP, TJOI, 结论 继续阅读

  6. 「HAOI2006」数字序列 - DP

    现在我们有一个长度为 n n 的整数序列 {ai} \{ a_i \} 。我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。

    于  BZOJ, DP, HAOI 继续阅读

  7. 「HAOI2007」分割矩阵 - 搜索

    将一个 n×m n \times m 的数字矩阵进行如下分割:将原矩阵沿某一条直线分割成两个矩阵,再将生成的两个矩阵继续如此分割(当然也可以只分割其中的一个),这样分割了 k1 k - 1 次后,原矩阵被分割成了 k k 个矩阵。(每次分割都只能沿着数字间的缝隙进行)原矩阵中每一位置上有一个分值,一个矩阵的总分为其所含各位置上分值之和。现在需要把矩阵按上述规则分割成 n n 个矩阵,并使各矩阵总分的均方差最小。请编程对给出的矩阵及 n n ,求出均方差的最小值。

    于  BZOJ, DFS, DP, HAOI, 搜索 继续阅读

  8. 「HAOI2007」上升序列 - DP + 贪心

    对于一个给定的 S={a1,a2,a3,,an} S = \{ a_1, a_2, a_3, \ldots , a_n \} ,若有 P={ax1,ax2,ax3,,axm} P = \{ a_{x_1},a_{x_2}, a_{x_3}, \ldots, a_{x_m} \} ,满足 x1<x2<<xm x_1 < x_2 < \ldots < x_m ax1<ax2<<axm a_{x_1} < a_{x_2} < \ldots < a_{x_m} ,那么就称 P P S S 的一个上升序列。如果有多个 P P 满足条件,那么我们想求字典序最小的那个。

    任务给出 S S 序列,给出若干询问。对于第 i i 个询问,求出长度为 Li L_i 的上升序列,如有多个,求出下标字典序最小的那个。

    于  BZOJ, DP, HAOI, 贪心 继续阅读

  9. 「NOIP2016」换教室 - Floyd + DP + 概率与期望

    对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

    在可以选择的课程中,有 2n 2n 节课程安排在 n n 个时间段上。在第 i i 1in 1 \leq i \leq n )个时间段上,两节内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci c_i 上课,而另一节课程在教室 di d_i 进行。

    在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n n 节安排好的课程。如果学生想更换第i节课程的教室,则需要提出申请。若申请通过,学生就可以在第 i i 个时间段去教室 di d_i 上课,否则仍然在教室 ci c_i 上课。

    由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i i 节课程的教室时,申请被通过的概率是一个已知的实数 ki k_i ,并且对于不同课程的申请,被通过的概率是互相独立的。

    学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m m 节课程进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程的申请结果来决定其他课程是否申请;牛牛可以申请白己最希望更换教室的 m m 门课程,也可以不用完这 m m 个申请的机会,甚至可以一门课程都不申请。

    因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课问时间从一间教室赶到另一间教室。

    牛牛所在的大学有 v v 个教室,有 e e 条道路。每条道路连接两间教室,并且是可以双向通行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。当第 i i 1in1 1 \leq i \leq n - 1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。

    现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

    于  DP, Floyd, NOIP, 概率与期望 继续阅读

  10. 「NOIP2010」引水入城 - BFS + DP

    在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政区划十分特殊,刚好构成一个 N N M M 列的矩形,如上图所示,其中每个格子都代表一座城市,每座城市都有一个海拔高度。

    为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。因此,只有与湖泊毗邻的第 1 1 行的城市可以建造蓄水厂。而输水站的功能则是通过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。

    由于第 N N 行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干旱区中不可能建有水利设施的城市数目。

    于  BFS, CodeVS, DP, NOIP, 线性 DP 继续阅读