动态规划题目合集

标签：le 题目 min sum times sim 动态合集 dp

3n多米诺问题

$dp[i]$ 表示前 $i$ 列的方案数，$dp2[i]$ 表示前 $i$ 列但是最上面一行缺一个的方案数。

$dp[i],dp2[i]$ 可以相互递推，而且刚好是矩阵递推。

矩阵快速幂优化。

Walk

有向无权图。求长度 $k$ 的路径条数。

我们发现邻接矩阵的 $k$ 次方各个元素求和就是路径条数。

矩阵快速幂。

古城之谜

状态定义：

$dp1[i]$ 表示前 $i$ 个字符，结尾是一个动词加上若干辅词，分成若干个句子，所得的最小句子数和单词数。（是一个 pair）

$dp2[i]$ 类似上方定义，但是是名词加上若干辅词。

初值：

除了 $dp1[0]$ 的 first = second = 0，其他都是 first = second = $+\infty$。因为文章开头一个必须是名词，所以开头之前就是要动词以接名词。

状态转移：

求 $dp[i]$ 时，枚举 $j$，使得 $s(j,i)$（$s[j]\sim s[i]$ 构成的字符串）是一个单词。
记 $str=s(j,i)$。

注：这里的 pair 取 min 是先按照句子数（first）比，first 相等按单词数单词数（second）比。$(a,b)$ 是 make_pair(a,b) 的简写，两个 pair 相加是把 first 和 second 对应相加。

$str$ 是辅词，$dp1[i]=\min(dp1[i],dp1[j-1]+(0,1))$，$dp2[i]=\min(dp2[i],dp2[j-1]+(0,1))$；
$str$ 是名词，$dp2[i]=\min(dp2[i],dp2[j-1]+(1,1),dp1[j-1]+(0,1))$；
$str$ 是动词，$dp1[i]=\min(dp1[i],dp2[i-1]+(0,1))$。

但是这太慢了，我们发现，枚举上一个单词的结尾时，我们不需要重新循环一遍组成单词来判断，我们可以使用 Trie 来优化这个操作。只需要把所有单词倒着插入 Trie 中，我们就可以利用 Trie 快速检查一个单词是否存在。

还要注意几个问题，我们的转移可能会导致最后一个句子里面不是名词开头，对此我们的应对方法是：枚举最后一个单词，如果是动词，就用前面的 dp2 加一个单词更新答案；如果是名词，就用 dp1 加一个单词更新答案。

知识点：

用 pair 数组 dp，可以同时记录两个答案

Trie 优化

铁球落地

先按照高度从矮到高把所有平台排序。

状态定义：

$dpl[i]$ 表示前 $i$ 个平台，且从第 $i$ 个平台的左端点（开始就先下落）出发，降落到地面所需的最短时间。

$dpr[i]$ 类似，但是是从右端点开始。

初值：

除了 $dpl[0]=dpr[0]=0$，其他都是 $+\infty$。

转移：

因为 $dpr$ 的转移显然和 $dpl$ 类似，这里只说 $dpl$。

枚举 $j:1\leq j < i$，看一下小球从左端点下落能不能落到平台 $j$ 上面，如果能，那么进行转移：$dpl[i]=\min(dpl[i],dpl[j]+l[i]-l[j],dpr[j]+r[j]-l[i])$，其中 $l[i]$ 表示平台 $i$ 的左端点 x 坐标，$r[i]$ 表示平台 $j$ 的右端点 x 坐标。（往左滚和往右滚两种取较小）

但是这太慢了，考虑优化。
我们发现，枚举 $j$ 的循环其实不必要，我们可以使用线段树。

具体而言，我们计算完 $dp[i]$ 之后，在线段树上把 $[l[i],r[i])$ 直接赋值为 $i$，这样我们在下次查询 $i+1$ 的左端点会落到哪里的时候，直接 $qry(l[i+1])$ 单点查询。
当然，这也意味这我们需要离散化每个平台的左右端点坐标。

可以这么做的原因，是我们按照高度排序了，所以如果一个平台上方有另一个更高的平台，被更高平台覆盖的部分一定不会被落到。

答案还需要处理一下，因为我们没有算小球一开始下落和滚动的时间。

知识点：

线段树优化

离散化

奶牛集合

换根 DP

物流运输

保安站岗

树形DP，$dp_{i,0/1/2}$ 表示以 $i$ 为根的子树全部覆盖，并且 $i$ 被覆盖自己的保安/被父结点的保安/被子结点的保安看守时的最小代价。

保安站岗弱化版

Arrays

这题蓝属实过分了吧（

$dp[i][0/1/2]$ 表示前 $i$ 个余 $0/1/2$ 的方案数。

AT_dp_x

先用贪心得知 $w+s$ 越小的越在上面。

然后 dp。

Mice and Holes

显然一个洞只会容纳连续的一段老鼠。把老鼠和洞都排序。

$dp[i][j]$ 表示前 $i$ 只老鼠前 $j$ 个洞的最小总距离。

$dp[i][j]=\displaystyle \min_{k\le c_j}\{dp[i-k][j-1]+\sum_{i-k+1\le x\le i} |P_j-p_x|\}.$

$P_j$ 为洞 $j$ 的位置，$p_x$ 为老鼠 $x$ 的位置。

发现当 $i$ 一定时，后面的求和可以前缀和优化。记为 $S_{i,j}$。发现这与 $k$ 无关，直接提出来。

$dp[i][j]=S_{i,j}+\min(dp[i-k][j-1]-S_{i,k})$。

这样就可以单调队列优化。

POJ2288：

题意：给定图带点权。找一条哈密顿路径权值最大。一条路径的权值定义：设路径为 $v_1v_2\dots v_n$，则权值为：$\sum a_{v_i}+\sum a_{v_i}a_{v_{i+1}}$，同时，如果 $v_i,v_{i+1},v_{i+2}$ 形成环，则权值还要加上 $a_{v_i}a_{v_{i+1}}a_{v_{i+2}}$。点个数 $\le 13$。

解法：状压 dp，$dp[i][j][S]$ 表示去过的点状态为 $S$，上一次到的点是 $i$，当前在 $j$ 的路径权值最大是多少。

关于三个点的 dp，一般可记录上一个和当前的，枚举下一个的时候统计。

EST

题意：给定一个序列 $a$，求一个序列 $b$，使得 $\sum |a_i-b_i|$ 最小，且 $b$ 可以分成恰好 $k$ 段，每一段内的数都相等。

$n\le 2000,k\le 25$。

显然一段内的 $b$ 都等于对应的 $a$ 中这一段的中位数。

考虑 $dp[i][j]$ 表示前 $i$ 个分成 $j$ 段，$\sum|a_i-b_i|$ 最小是多少。

枚举第 $j$ 段的开头元素 $a[l]$，$dp[i][j]=\min\{dp[l-1][j-1]+cost(l,i)\}$。其中 $cost(l,i)$ 表示 $\sum_{x=l}^i|a_x-a_{mid}|,a_{mid}$ 是 $a_l\sim a_i$ 的中位数。

其他部分 $O(n^2k)$ 可以过，但是求 $cost(l,i)$ 必须进行优化，不能暴力。

求 $a_{mid}$，我们可以用对顶堆，同时 $l$ 从 $i$ 到 $1$ 枚举可以动态求中位数。

把 $\sum|a_x-a_{mid}|$ 分成两半：一种是 $a_x\ge a_{mid}$ 的，一种是 $a_x< a_{mid}$ 的。我们只需要知道这两种数的个数，和这两种数的和就行。假设 $a_x\ge a_{mid}$ 的有 $cbig$ 个，这种 $a_x$ 的和是 $sbig$，$a_x<a_{mid}$ 类似定义。

则 $\sum|a_x-a_{mid}|=sbig-cbig\times a_{mid}+csmall\times a_{mid}-ssmall$。

其实我们只需要知道 $cbig,sbig$ 就行，因为 $csmall,ssmall$ 可以做差求出。

那如何快速求 $cbig,sbig$？我们可以用树状数组，这是很经典的问题。

Tower of Hay 与题解

绝世好题（只是叫这个名字而已）

部分分显然就是 $dp[i]$ 表示前 $i$ 个的最长长度，但是这是 $O(n^2)$ 的。

在状态定义上面优化（这种优化一般比较巧）：$dp[i][j]$ 表示前 $i$ 个数选的子序列，要求子序列最后一项的第 $j$ 个二进制位是 $1$ 的最长长度。

初始值全部设成 $0$。

转移的时候，先让所有 $dp[i][j]=dp[i-1][j]$。接着对 $a[i]$ 所有是 $1$ 的位 $x$，$dp[i][x]++$。然后对 $a[i]$ 所有是 $1$ 的位 $x$ 的 $dp[i][x]$ 求出最大值，把这些 $dp[i][x]$ 全部赋值成这个最大值。

262144

第一眼的想法肯定是区间 dp，但是这题不仅碍于数据范围，而且用区间 dp 也不知道两个子问题区间的长度。

既然不知道区间长度，不如直接设成 $dp$ 的值。（下面定义成右端点也是等价的）

状态定义：$dp[i][j]$ 表示以 $i$ 为左端点，能合成出 $j$ 的右端点最左是哪里。如果合成不出来就是 $0$。

初值 $dp[i][a[i]]=1$，转移 $dp[i][j]=dp[dp[i][j-1]][j-1]$。

感觉有点像倍增了，这个转移方程正确吗？

要合成出 $j$，显然只能 $(j-1),(j-1)\rightarrow j$，所以我们只需要搞出两个能合成出 $j-1$ 的区间，尽可能最短即可。

定义范围 $dp[1\sim n][1\sim 58]$，为什么是 $58$？因为 $262144=2^{18}$，所以合成的数最多是 $40+18=58$。

Sue 的小球

类似的题：关路灯

最大价值 = 总价值 - 最小损耗

$dp1[i][j]$ 表示从 $j$ 直接走到 $i$ 所有灯的最小损耗。

$dp2[i][j]$ 表示从 $i\sim j$ 中间一个点走到 $j$ 再走回 $i$ 所有灯的最小损耗。

20个问题

注意本题的多测

$dp[S][U]$ 表示询问了 $S$ 中的位，且得到的答案存在 $U$ 里面，最坏情况最少要问多少次确定答案。

$S$ 某一位为 $0$ 表示没有询问，没有询问的位在 $U$ 中设定为 $0$；$S$ 某一位为 $1$，$U$ 中对应位代表询问得到的答案。

预处理一个 $cnt[S][U]$：表示有多少个数满足询问 $S$ 中的位且答案为 $U$。

目标状态：$dp[0][0]$。

递推：若 $cnt[S][U]=1$，则 $dp[S][U]=0$；否则枚举 $j\not\in S$，$dp[S][U]\leftarrow \min(dp[S][U],\max(dp[S+2^j][U],dp[S+2^j][U+2^j]) + 1)$。

集合选数

巧妙！

构建一个方格图来描述这个不能选的关系。对于每个数抽象为一个方格，它乘三代表的数在它右边，它乘二代表的数在它下面。于是就构造出了若干个方格图。

题目的条件等价于相邻格子不能选。

由乘法原理，我们只要求出每个方格图的方案数再乘起来就行。

而对于单个方格图，可以状压 dp，是个经典模型。

Max Correct Set

结论：一定存在一个最优解，满足如果 $p$ 选了，$p+x+y$ 也被选。

有了这个结论就能直接状压了。配合上：环形，不停 + x，如果超过 y 就 - y 这个理解。可以变成 $O(x+y)$ 的环形 DP。

注意处理 $gcd(x,y)>1$ 的情况：$ans(n,x,y)=((g - n \% g) * ans(n / g, x / g, y / g)) + ((n \% g) * ans(n / g + 1, x / g, y / g)))$

障碍物多米诺

给定 $n\times m$ 的网格，上面有障碍物，有多少种方法放入一个 $1\times 2$ 的矩形。

前缀和。

分两半

给定一个序列，判断是否能通过删除若干数使得整个序列不能分成和相等的两半。

先用可行性背包 DP 出一开始能不能分成和相等的两半——如果不行，就不用删。

否则，我们考虑到如果总和是奇数，肯定不能分成两半。所以尝试删除一个奇数。而如果全部都是偶数，我们将每个数都除以二，递归再看。

2×m 哈密顿路

给定一个 $2\times m$ 的方格，每个格子有一个锁定时间 $a_{i,j}$，表示 $a_{i,j}$ 秒后这个格子才开放。

初始在 $(1,1)$，每一秒可以移动一格或者原地不动。求每个格子恰好走过一遍，所需的最小时间。

玩家

你要打怪兽了，有 $C\le 10^6$ 个金币。有 $n$ 种战士，攻击力、血量、花费为 $d_i,h_i,c_i$。并且每多花 $c_i$ 个金币，攻击力就多一个 $d_i$。只能选一种战士作战。

有 $q$ 个询问，每次给出一个血量 $H$ 攻击 $D$ 的怪物。怪物杀掉战士需要 $h_i/D$ 的时间，战士杀掉怪物需要 $H/d_i$ 的时间。求杀掉怪物且战士不死的最小花费。

只要 $h_i\times d_i$ 越大，就越容易干掉怪物。我们将 $h_i\times d_i$ 称为战士的能力值。

鉴于 $C$ 比较小，可以考虑对每一个花费都求出能获得的最大能力值。注意只能选一种战士作战。

$dp[i]$ 表示恰好用 $i$ 个金币能获得的最大能力值。初值 $dp[c_i]=\max\{h_i\times d_i\}$。

递推：$dp[i\times j]=\max(dp[i\times j], dp[i]\times j)$。

构造 1~5

给定序列 $a_i$，要求构造序列 $b$，满足：

$b_i\in [1,5]\cap \mathbb{Z}$。
若 $a_i=a_{i+1}$，$b_{i}\neq b_{i+1}$。
若 $a_i>a_{i+1}$，$b_{i}> b_{i+1}$。
若 $a_i<a_{i+1}$，$b_{i}< b_{i+1}$。

可行性 DP：$dp[i][j]$ 表示考虑前 $i$ 个元素，$b_i=j$ 是否可行。

删数位

给定一个长度 $\le 10^5$ 的大数。可以从中挑连续的一段数位删去，将剩下的数位构成的新数统计入总和中。问这个总和是多少。（允许前导零）

考虑每一位的贡献。如果被删了，肯定没有贡献。所以贡献可以分为：只删前面和只删后面。

只删前面：很简单，这一位的贡献始终不变，前面共有 $2^{x}-1$ 种方法删，所以这一位的贡献是 $(2^x-1)\times a_{x+1}\times 10^{len-x-1}.$

只删后面：容易用递推的方法做。

倍增

给定长度 $n\le1000$ 的序列 $a$ 和 $b$，$a$ 初始全是 $1$，$b_i\le 1000$。每次操作可以选一个位置 $pos$ 和正整数 $x$，$a_{pos}\leftarrow (a_{pos}+\lfloor \dfrac{a_{pos}}{x}\rfloor)$。共可以进行 $k\le 10^6$ 次操作。
若最后 $a_i=b_i$，可以获得 $c_i\le 10^6$ 的收益。

求最大收益。

首先可以 $O(n^2)$ 预处理 $1\rightarrow x$ 所需的此时 $f[x]$。

然后就变成01背包模型。但是这样是 $O(nk)$ 的，会炸。

进一步观察，其实上涨的幅度很快，根本用不到 $k$ 次操作就能长好了。所以如果 $k\ge \sum f[b_i]$，可以直接求和输出，这样就优化到约 $O(12n^2)$。

抢救

给定 $n$ 个物品，每个物品有一个死亡时间，拯救需要的时间和拯救获得的价值。

这题很像建筑抢修，区别是物品有各自的拯救价值。但关键点都是：按物品死亡时间升序排序。

排完序就是 DP 了。$dp[i][j]$ 表示前 $i$ 个物品拯救完最后一个物品时间不晚于 $j$ 的最大收益。

覆盖

题意：给定一个颜色序列。要选定一个位置 $pos$，不停把 $pos$ 所在的颜色连通块改成另一个颜色。问最少需要多少次操作，可以改成全部同色。

很自然的想法就是区间 DP，$dp[i][j]$ 表示将 $[i,j]$ 改成同色的最小操作数量。

初值 $dp[i][i]=0$。

若 $i,j$ 同色，$dp[i][j]\leftarrow \min(dp[i][j],dp[i+1][j-1]+1)$。

同时 $dp[i][j]\leftarrow \displaystyle \min_{k=i}^{j-1}\{dp[i][k]+dp[k][j]+1\}$。

注意：这么写是对的，因为是选定一个位置不停改。

完成任务

有 $n$ 个任务，第 $i$ 个要在 $a_i$ 时刻前做完。

有 $m$ 个计划，第 $i$ 个可以花 $t_i$ 的时间让任务 $e_i$ 增加 $p_i\% \;\;(p_i\le 100)$ 的完成度。当一个计划的完成度 $\ge 100\%$，这个任务就完成了。

判断是否能让每个任务完成。并且可以的话，输出执行计划的方案。$n,m\le 10^5,e_i\le n, t_i\le 10^9$.

明显看出可以把所有任务按照 $a_i$ 升序排序，把所有计划分成一个一个任务的来看。

对于一个任务，我们的问题变成：有 $x$ 个计划，每一个计划有需要花费的时间和可以获得的完成度。用 $a_i$ 的时间最多能达到多少完成度？

这不就是 01背包吗？但是 $a,t$ 的范围都很大。我们可以反着来，$dp[i][j]$ 表示前 $i$ 个达到 $j$ 的百分比，至少需要多少时间。（$j\le 200$）

回文串判断

给定字符串，求出 $[l,r]$ 内的子串包含多少个回文串。$|S|\le 5000$。

可行性DP：$dp[i][j]$ 表示 $[i,j]$ 是否是回文串。询问 $[l,r]$ 内的子串，可以看作是 $\displaystyle \sum_{i=l}^r \sum_{j=i}^r dp[i][j]$，类似二维前缀和。

回文串计数

给定字符串，求出有多少个不相交的的回文子串对。$|S|\le 2000$。

和上一题一样，$dp[l][r]$ 表示 $S[l\sim r]$ 是否是回文串。然后令 $cnt[i]=\displaystyle\sum_{j=i}^n dp[i][j]$，此时 $cnt[i]$ 记录以第 $i$ 个字符开头的回文串个数。

对 $cnt$ 求后缀和，此时 $cnt[i]$ 记录所有开头在 $i$ 之后的回文串个数。

枚举所有回文串 $S[l\sim r]$，累加 $cnt[r+1]$。最后输出即可。

祖玛

给定一个字符串，每次可以挑一个回文子串删除，剩下的会拼起来。问最少删除几次可以删光。$n\le 500$

初值：$dp[i][i]=1,dp[i][i+1]=1+(s[i]\neq s[i+1])$。

递推：若 $s[i]=s[j]$，$dp[i][j]\leftarrow dp[i+1][j-1]$。（删除 $[i+1,j-1]$ 的最后一次搭上 $i,j$ 即可）

同时任何时候，$dp[i][j]\leftarrow dp[i][k]+dp[k+1][j]$。

括号涂色

给定一个匹配的括号序列，每一个括号可以不涂色或者涂两种颜色之一。每一对匹配的括号恰好有一个要涂色，相邻两个括号不能涂同色。求方案数。$|s|\le 700$。

$dp[i][j][x][y]$ 表示 $s[i\sim j]$ 且两端颜色分别为 $x,y$ 的方案数。

倒水

有 $n$ 个杯子，第 $i$ 个杯子容积 $a_i$，初始有 $b_i$ 的水。你可以从一个杯子向另一个杯子倒水，但是 $x$ 升水倒过去，会有 $\dfrac{x}{2}$ 升的水损失。

对于 $p=1\sim n$，求出经过若干次倒水后，选出 $p$ 个杯子，其中水总和最大是多少。

显然当我们选定之后，要尽量从没选的杯子往选了的杯子里倒水。

记原本总水量为 $B$，选了的杯子的集合为 $S$，选了的杯子的容积之和为 $A_S$，选了的杯子目前有 $B_S$ 的水。

则最终的答案是 $\min(A_S,B_S+(B-B_s)/2)=\min(A_S,B/2+B_S/2)$。

因此我们要让 $B_S$ 大。

$dp[i][k][A]$ 表示前 $i$ 个杯子，选出 $k$ 个杯子，容积和为 $A$ 的情况下，$B_S$ 最大是多少。

初值 $dp[0][0][0]=0$。

$dp[i][k][A]=\max(dp[i-1][k][A],dp[i-1][k-1][A-a[i]]+b[i]).$

清除字符串

题意：每次可以删除一个字符块，求最小操作次数删完。

$dp[i][j]$：删光 $s[i\sim j]$ 的最小操作次数。

$dp[i][i]=1,dp[i][i+1]=1+1\times[s[i]\neq s[j]]$。

$dp[i][j]\leftarrow \min(dp[i][k]+dp[k+1][j])$。

$dp[i][j]\leftarrow dp[i+1][j]+1$。

$dp[i][j]=\min(dp[i+1][k-1]+dp[k][j])$，当 $s[i]=s[k]$。（把 $s[i+1\sim k-1]$ 删掉，这样 $s[i]$ 和 $s[k]$ 就相邻，可以视作一个字符）

异或

给定一棵树，每个点有 0/1 的点权。第 $t$ 时刻，每个节点的点权变成第 $t-1$ 时刻它所有直接子节点的点权的异或和。

一个时刻 $t$ 的权重定义为 $t$ 时刻所有节点的点权和，一个对点权的安排 $A$ 的权重 $F(A)$ 定义为 $t=0\sim +\infty$ 时的权重之和。对于所有点权的安排 $A$，求出 $\sum F(A)$。

观察到，第 $1$ 时刻点权是儿子们的异或和，第 $2$ 时刻点权是孙子们的异或和 ……

定义 $s_i$：叶节点的 $s=1$，其余的 $s_u=\max\{s_{son}\}+1$。

显然对于节点 $u$，只有 $0\sim s_u-1$ 时刻，它的点权可能是 $1$。（过了 $s_u$，子孙深度就不够了）

假设某时刻 $u$ 需要用到 $cnt$ 个子孙来异或自身的贡献。下证：这些子孙的点权安排有 $2^{cnt-1}$ 种可能使得 $u$ 点权为 $1$。

将一个使得 $u$ 点权为 $1$ 的01序列写成一个二进制数 $x$，$x$ 和 $x\bigoplus 1$ 形成一一对应，且 $x$ 和 $x\bigoplus 1$ 恰好有一个有贡献。所以有一半的可能使得 $u$ 点权为 $1$。

既然这里有 $2^{cnt-1}$ 种方法，算上其他的点随便安排，就有 $2^{n-1}$ 种可能。

因此我们用 DP 求出 $\{s\}$，然后计算 $(2^{n-1})\sum s_i$ 即可。

补括号

给定一个长度 $m$ 的括号序列，要求在两侧补上一些字符使得变成长度 $n$ 的合法括号序列。求方案数。$n-m\le 2000$。

预处理 $dp[i][j]$：$i$ 个字符，一共左括号比右括号多 $j$ 个，且每一个前缀左括号都不比右括号数量少，的括号序列有多少个。

$dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]$，若 $j=0$ 就 $=dp[i-1][j+1]$。

然后枚举放在左侧的括号序列长度、左括号比右括号多的数量。
乘一下累加即可。

路径

给出 $n$ 个点，$m$ 条边的有向图。

求出一条任意起点、途中不能经过之前走过的点，并且包含 $k$ 个点的权值最小的路径，如果不存在就输出 $-1$ 。

边 $(u, v)$经过点 $x$，当且仅当 $min(u,v) < x < max(u,v)$ 。

$1 \leq n,k \leq 80, 0\leq m\leq 2000, 1\leq u_i, v_i \leq n, 1\leq c_i\leq 1000$。

走一条边，就会把能走的区间分开。考虑 $dp[i][l][r][0/1]$ 表示当前已经经过了 $i$ 个点，可以走的区间是 $(l,r)$，0表示当前在 $l$，1表示当前在 $r$。

初值：$dp[1][0][i][1]=dp[1][i][n+1][0]=0$。

递推：适合刷表法。$dp[i][l][r][0/1]+edg\_l.val\rightarrow dp[i + 1][l][edg\_l.to][1],dp[i+1][edg_l.to][r][0]$，$dp[i][l][r][0/1]+edg\_r.val\rightarrow dp[i + 1][l][edg\_r.to][1],dp[i+1][edg_r.to][r][0]$。

答案：$\displaystyle\min_{0\le l<r\le n+1}\{dp[k][l][r][0/1]\}$。

注意是开区间。

角斗场

有 $n$ 个人，每个人有初始血量。每个回合，所有还活着的人会同时对场上其余人造成 $1$ 伤害，然后血量 $\le 0$ 的死掉。

现在要你指派每个人的初始血量，要求在 $[1,x]$ 之间。然后进行若干回合，使得最后无人生还。求方案数。

$dp[i][j]$ 表示有 $i$ 个人，最大血量为 $j$ 的方案数。

若 $i-1\ge j$，随便安排人的血量即可。$dp[i][j]=j^i-(j-1)^i$。

否则，枚举剩下的人的个数，并且此时剩余最大血量为 $j-i+1$。所以 $dp[i][j]=\sum dp[k][j-i+1]\times (i-1)^{i-k}\times C_i^k$。

极差

给定序列 $a$，对其重排，使得 $\sum\limits_{i=1}^{n} (\max\limits_{j=1}^ia_j-\min\limits_{j=1}^i a_j)$ 最小。

观察发现，最后一个位置必然是最大值或者最小值。

于是对 $a_i$ 先升序排序，$dp[i][j]$ 表示 $a_i\sim a_{i+j-1}$ 的答案。