Menci

眉眼如初,岁月如故

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


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

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

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

  2. 「HAOI2007」理想的正方形 - 单调队列

    有一个 n×m n \times m 的整数组成的矩阵,现请你从中找出一个 k×k k \times k 的正方形区域,使得该区域所有数中的最大值和最小值的差最小。

    于  BZOJ, HAOI, 单调队列 继续阅读

  3. 「BZOJ 3156」防御准备 - 斜率优化 DP

    我们定义战线为一条长度为 n n 的序列,在这条战线上共设有 n n 个检查点,从左到右依次标号为 1 1 n n 。一个战线为合法战线当且仅当任意一个检查点可以通过安全检查。对于第 i i 个点,通过安全检查的方法有两种,第一种是放置一个守卫塔,这将花费 c(i) c(i) 的费用,第二种方式是放置一个木偶,放置木偶的花费等于这个检查点右侧的第一个守卫塔到它的距离。第 n n 个点只能放置守卫塔。求最小的战线花费值。

    于  BZOJ, DP, 单调队列, 斜率优化 继续阅读

  4. 「CEOI2004」锯木厂选址 - 斜率优化 DP

    从山顶上到山底下沿着一条直线种植了 n n 棵老树。当地的政府决定把他们砍下来。为了不浪费任何一棵木材,树被砍倒后要运送到锯木厂。 木材只能按照一个方向运输:朝山下运。山脚下有一个锯木厂。另外两个锯木厂将新修建在山路上。你必须决定在哪里修建两个锯木厂,使得传输的费用总和最小。假定运输每公斤木材每米需要一分钱。

    于  CEOI, COGS, DP, 单调队列, 斜率优化 继续阅读

  5. 「BZOJ 1597」土地购买 - 斜率优化 DP

    农夫 John 准备扩大他的农场,他正在考虑 N N 1N50000 1 \leq N \leq 50000 )块长方形的土地。每块土地的长宽满足(1 1 \leq 长、宽 1000000 \leq 1000000 )。每块土地的价格是它的面积,但 FJ 可以同时购买多快土地。这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 3×5 3 \times 5 的地和一块 5×3 5 \times 3 的地,则他需要付 5×5=25 5 \times 5 = 25 。FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费,他需要你帮助他找到最小的经费。

    于  BZOJ, DP, 单调队列, 斜率优化 继续阅读

  6. 「ZJOI2007」仓库建设 - 斜率优化 DP

    i i 个工厂目前已有成品 Pi P_i 件,在第 i i 个位置建立仓库的费用是 Ci C_i 。对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于公司产品的对外销售处设置在山脚的工厂 N N ,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送 1 1 个单位距离的费用是 1 1 。假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

    1. 工厂 i i 距离工厂 1 1 的距离 xi x_i (其中 x1=0 x_1 = 0 );
    2. 工厂 i i 目前已有成品数量 pi p_i
    3. 在工厂 i i 建立仓库的费用 ci c_i

    请你帮助公司寻找一个仓库建设的方案,使得总的费用(建造费用 + 运输费用)最小。

    于  BZOJ, COGS, DP, ZJOI, 单调队列, 斜率优化 继续阅读

  7. 「APIO2010」特别行动队 - 斜率优化 DP

    一支部队由 n n 名预备役士兵组成,士兵从 1 1 n n 编号,要将他们拆分成若干特别行动队,同一队中队员的编号应该连续。

    士兵 i i 的初始战斗力为 xi x_i 一支特别行动队的初始战斗力 x x 为各士兵初始战斗力之和。一支特别行动队的战斗力会被修正为 x=Ax2+Bx+C x' = Ax ^ 2 + Bx + C ,其中 A A B B C C 已知,A<0 A < 0

    求出将所有士兵组成若干特别行动队的最大总战斗力。

    于  APIO, BZOJ, DP, 单调队列, 斜率优化 继续阅读

  8. 「HNOI2008」玩具装箱 - 斜率优化 DP

    P 教授有编号为 1 1 ~ N N N N 件玩具,第 i i 件玩具经过压缩后变成一维长度为 Ci C_i 。为了方便整理,P 教授要求在一个一维容器中的玩具编号是连续的。如果将第 i i 件玩具到第 j j 个玩具放到一个容器中,那么容器的长度将为 x=ji+k=ijCk x = j - i + \sum\limits_{k = i} ^ j C_k 。如果容器长度为 x x 。其制作费用为 (xL)2 (x - L) ^ 2 。其中 L L 是一个常量。P 教授不关心容器的数目,他可以制作出任意长度的容 器,甚至超过 L L 。但他希望费用最小。

    于  BZOJ, COGS, CodeVS, DP, HNOI, 单调队列, 斜率优化 继续阅读

  9. 「SDOI2016」征途 - 斜率优化 DP

    Pine 开始了从 S S 地到 T T 地的征途。
    S S 地到 T T 地的路可以划分成 n n 段,相邻两段路的分界点设有休息站。
    Pine 计划用 m m 天到达 T T 地。除第 m m 天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。
    Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。
    帮助 Pine 求出最小方差是多少。

    设方差是 v v ,可以证明,v×m2 v \times m ^ 2 是一个整数。为了避免精度误差,输出结果时输出 v×m2 v \times m ^ 2

    于  BZOJ, COGS, DP, SDOI, 单调队列, 斜率优化 继续阅读

  10. 「BZOJ 2442」修剪草坪 - 线性 DP + 单调队列

    FJ 有 N )只排成一排的奶牛,编号为 1N。每只奶牛的效率是不同的,奶牛 i 的效率为EiE_i )。

    靠近的奶牛们很熟悉,因此,如果 FJ 安排超过 K 只连续的奶牛,那么,这些奶牛就会罢工去开派对。因此,现在 FJ 需要你的帮助,计算 FJ 可以得到的最大效率,并且该方案中没有连续的超过 K 只奶牛。

    于  BZOJ, CodeVS, DP, USACO, 单调队列, 线性 DP 继续阅读