题意给出一个数字串，要求用逗号将其分成若干个严格递增的数。如果有多解要求最后一个数最小，如果还有多解要求字典序最大。数字串长度 $\le 500$ 。题解先正着推出最后一个最小的数。用 $f[i]$ 代表以 $i$ 结尾的数的最近的开头，可以逆序枚举 $j$ ，如果 $[f[j-1],j-1] < [j,i]$ ，那么 $f[i]=j$ 。然后反着推一个最大的数。用 $g[i]$ 表示...
题意有形成环形的 $N$ 个机器人工厂，购买机器人的价格为 $V_i$ 。连接 $i\rightarrow i+1$ 的道路编号为 $i$ ，在时间 $j$ 的金币数为 $s[i][j]$ 。每次可以在任意工厂购买一个机器人，机器人最多可以走 $P$ 条边，并收集边上的金币。不能同时存在多个机器人。求 $M$ 的时间内最多能收集多少金币。$N,M\le 1000$ 。题解用 $f[i]$ 表...
题意你正在玩一个关于长度为 $n$ 的非负整数序列的游戏。这个游戏中你需要把序列分成 $k + 1$ 个非空的块。为了得到 $k + 1$ 块，你需要重复下面的操作 $k$ 次：选择一个有超过一个元素的块（初始时你只有一块，即整个序列）选择两个相邻元素把这个块从中间分开，得到两个非空的块。每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。$n\le 10000...
题意有 $N$ 块矩形土地，面积为 $W_i\times H_i$ 。可以购买单个土地，价格为面积；也可以将多个土地合并起来买，价格为 $\max W\times \max H$ 。要将所有土地买下来，求最小花费。$N\le 50000$ 。题解对于两块土地 $i,j$ ，如果 $H_i\le H_j,W_i\le W_j$ ，那么买 $j$ 的时候顺便把 $i$ 带上就行了，$i$ 就可以...
题意有 $N$ 个商店，每个商店在 $X_i$，有 $F_i$ 个物品，价格为 $C_i$ 元。如果车上有 $P$ 个物品，每单位距离的运输费用为 $P^2$ 。从 $1\rightarrow E$，要求买 $M$ 个物品，求最小花费。$N,E\le 500 \ , \ X_i\le E$ 。题解先把 $E$ 看成一个商店，各项属性为 $X_i=E \ , \ F_i=C_i=0$ 。然后把...
题意有 $N$ 个点，从 $1$ 开始跳，跳到高度比当前矮的点免费，否则消耗 $1$ 。有 $M$ 次询问，每次给出最长能跳的距离，求跳到 $N$ 的最小花费。$N\le 10^6 \ , \ M\le 25$ 。题解用 $f[i]$ 表示跳到 $i$ 的最小花费，则$$f[i]=\min_{i-j\le q} \begin{cases} f[j] \ (H_j > H_i) \\ ...
题意有 $N$ 个数，可以进行 $K$ 次操作，每次可以选择一个区间，把其中所有数 $+1$ 。求最后最长不降子序列的长度。$N\le 10000 \ , \ K\le 500$ 。题解可以发现，每次选择区间的右端点一定是 $N$ ，否则就可能出现答案减小的情况，而不可能会增加。用 $f[i][j]$ 表示第 $i$ 个数被操作了 $j$ 次 ，前 $i$ 个数的最优情况。可以得到方程：$$...
题意有 $N$ 张卡片，使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格，如果跳到就输了，求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子，很容易想出状压方程：$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题意有 $N$ 个人要排队，要求一队的站在一起，共有 $M$ 队。调整队列的方法为让一部分人出队，再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压，用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ，设之前排到了第 $l$ 个人，那么现在要排的是 $[l+1,...
题意有 $N$ 个人去执行 $N$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。（直接用题面）$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ，枚举任务 $j$ ，很容易得到方程：$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零，可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ，状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品；预处理出 $v[i][j]$ 表示硬币 $i$ ，从 $j$ 物品开始买，能买到哪个物品；枚举当前用的硬币 $...
题意在一棵 $N$ 个点的树上放 $K$ 个监听器，每个监听器可以监听与它直接相连的节点，但不能监听自己。要求所有节点都被监听，求方案数。$N\le 100000 \ , \ K\le 100$ 。题解真·毒瘤题目。用 $f[x][i][0/1][0/1]$ 表示以 $x$ 节点为根的子树中除了 $x$ 都被监听了，放了 $i$ 个监听器，$x$ 上放没放监听器，$x$ 有没有被监听到 的方...
题意将一棵 $N$ 个点的树上 $K$ 个点染黑，另外的点染白。求黑点两两之间距离和加上白点两两之间距离和的最大值。$N,K\le 2000$ 。题解考虑每一条边的贡献，即为 边权 $\times ($ 一侧的黑点个数 $\times$ 另一侧的黑点个数 $+$ 一侧的白点个数 $\times$ 另一侧的白点个数 $)$ 。用 $f[x][i]$ 表示以 $x$ 为根的子树，黑点有 $i$ ...
题意有 $N$ 个小球，每个小球的坐标为 $(x_i,y_i)$ ，即水平为 $x_i$ ，高度为 $y_i$ ， 每秒会以 $v_i$ 的速度下落。人所在的初始位置为 $x_0$ ，每秒可以移动一个单位。当人移动到小球下面的时候就可以接住这个小球并获得分数，分数为小球当前高度的 $\dfrac{1}{1000}$ 。要求接住所有小球，求最高分数。$N\le 1000$ 。题解比较容易想到区...
题意可以用 $x(s)$ 来表示有 $x$ 个字符 $s$ ，可以在括号内嵌套和拼接。求一个字符串的最短折叠长度。字符串长度 $N\le 100$ 。题解设需要处理的字符串为 $S$ ，用 $f[l][r]$ 表示折叠 $S_l..S_r$ 的最短长度。显然可以从两个字符串拼接而来。枚举断点 $k$ ，$f[l][r]=\min(f[l][r],f[l][k]+f[k+1][r])$ 。也可...