「CC JUMP」Jump mission-DP + 动态凸包 + 树状数组

有 $N$ 座山排成一排,每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$,高度为 $H_i$。
大厨从第一座山出发,目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上($i < j, P_i < P_j$),并花费 $(H_i - H_j) ^ 2$ 的能量,当大厨处于第 $i$ 座山时,他还会花费 $A_i$ 的能量($A_i$ 可以为负)。

求最小能量花费。

「模拟测试」20171030

T2 Game

甲乙两个人轮流那一些物品,甲先手,他可以拿走 $1$ 或 $2$ 个物品。对于后面,若前一个人拿走 $k$ 个物品,当前的人可以拿走 $k$ 或 $k + 1$ 个物品,甲乙的策略都是让自己尽量比别人拿的物品的价值高,求最优策略下,甲最多比乙多拿多少?

「模拟测试」大逃杀

一棵树,经过一条边花费 $c_i$ 的时间,某些点上有障碍,经过额外花费 $t_i$ 时间,每个节点有 $w_i$ 的价值,求 $T$ 秒后获得的最大价值。

「UVA 10453」Make Palindrome-区间 DP

给定一个长度为 $n$ 的字符串,你需要在任意位置添加尽量少的字符,使新串是回文串。输出最少添加的字符个数以及新串。

「UVA 10163」Storage Keepers-DP

有 $n$ 个仓库,让 $m$ 个人来看管。一个仓库只能由一个人来看管,一个人可以看管多个仓库。
每个人有一个能力值 $p_i$,如果他看管 $k$ 个仓库,那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管,那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣,问所有仓库的安全值最高是多少,在安全值最高的情况下,求雇佣的最少价钱。

「SuperOJ 1998」「模拟测试」矩阵-DP

有一个 $n \times m$ 的矩阵,请你选出其中 $k$ 个子矩阵,使得这个 $k$ 个子矩阵分值之和最大。注意:选出的 $k$ 个子矩阵不能相互重叠。

「UVA 11404」Palindromic Subsequence-DP

给出一个字符串,输出其字典序最小的最长回文子序列。

「UVA 11552」Fewest Flops-DP

给出一个字符串,把它分成 $k$ 块,块内可以任意排序,连续的相同字母算作一段,求最终字符串中的最小段数。

「BZOJ 2064」分裂-状压 DP

给定一个初始集合和目标集合,有两种操作:

  1. 合并集合中的两个元素,新元素为两个元素之和
  2. 分裂集合中的一个元素,得到的两个新元素之和等于原先的元素

要求用最小步数使初始集合变为目标集合,求最小步数。

「BZOJ 4518」征途-dp + 斜率优化

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

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

「HDU 3709」Balanced Number-数位 dp

求 $[l, r]$ 中平衡数的个数,平衡数就是一某一位为支点,两侧的力矩相等。

「BZOJ 1010」玩具装箱-斜率优化

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

「CC GRAPHCNT」-支配树

给定一个 $N$ 个点 $M$ 条边的有向图。统计无序对 $(X, Y)$ 的个数,其中 $(X, Y)$ 满足存在一条从 $1$ 到 $X$ 的路径,和一条 $1$ 到 $Y$ 的路径,且两路径除 $1$ 外无公共点。

「BZOJ 2286」「SDOI 2011」消耗战-虚树

一棵 $n$ 个点,边带权的树,$m$ 次询问,每次给出 $k$ 个关键点,求割掉最小代价的边使 $1$ 号点不能到达任何关键点。

「ARC 070E」NarrowRectangles-斜率优化

二维坐标系中有 $n$ 个矩形,第 $i$ 个矩形在水平方向上覆盖 $[l_i, r_i]$,在竖直方向上覆盖 $[i - 1, i]$,我们要水平移动这些矩形使得它们全部连通,水平移动的花费是移动的距离,求最小费用。

「补档计划」动态规划

dp 太弱,先补动规专题…

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×