Menci

眉眼如初,岁月如故

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


  1. 「HAOI2006」数字序列 - DP

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

    于  BZOJ, DP, HAOI 继续阅读

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

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

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

  3. 「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, 贪心 继续阅读

  4. 「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, 概率与期望 继续阅读

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

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

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

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

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

  6. 「HAOI2008」木棍分割 - 二分 + DP

    n n 根木棍,第 i i 根木棍的长度为 Li L_i n n 根木棍依次连结了一起,总共有 n1 n - 1 个连接处。现在允许你最多砍断 m m 个连接处,砍完后 n n 根木棍被分成了很多段,要求满足总长度最大的一段长度最小,和有多少种砍的方法使得总长度最大的一段长度最小。

    于  BZOJ, DP, HAOI, 二分 继续阅读

  7. 「HAOI2008」硬币购物 - 背包 DP + 容斥原理

    一共有 4 4 种硬币。面值分别为 c1,c2,c3,c4 c_1, c_2, c_3, c_4 。某人去商店买东西,去了 n n 次。每次带 di d_i ci c_i 硬币,买 si s_i 的价格的东西。请问每次有多少种付款方法?

    于  BZOJ, DP, HAOI, 容斥原理, 数学, 背包 DP 继续阅读

  8. 「ZJOI2008」生日聚会 - DP

    对于任意连续的一段,男孩与女孩的数目之差不超过 k k 。假设参加 party 的人中共有 n n 个男孩与 m m 个女孩,求方案总数。

    于  BZOJ, DP, ZJOI 继续阅读

  9. 「SCOI2009」游戏 - 群论 + 背包 DP

    windy 学会了一种游戏。对于 1 1 N N N N 个数字,都有唯一且不同的 1 1 N N 的数字与之对应。最开始 windy 把数字按顺序 1,2,3,,N 1, 2, 3, \ldots, N 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,N 1, 2, 3, \ldots, N

    如:1,2,3,4,5,6 1, 2, 3, 4, 5, 6 对应的关系为

    {122331455466 \begin{cases} 1 \rightarrow 2 \\ 2 \rightarrow 3 \\ 3 \rightarrow 1 \\ 4 \rightarrow 5 \\ 5 \rightarrow 4 \\ 6 \rightarrow 6 \end{cases}

    windy 的操作如下:

    这时,我们就有若干排 1 1 N N 的排列,上例中有 7 7 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

    于  BZOJ, DP, SCOI, 数学, 群论, 背包 DP 继续阅读

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

    求仙人掌图的直径。

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