AtcoderDP1
收录非计数 dp 题。
[ABC227F] Treasure Hunting（2323）
Problem
给你一个 \(N \times M\) 的矩阵，你需要从坐标 \((1,1)\) 走到坐标 \((N,M)\) 去，每次只能向右或者向下走。
坐标 \((i,j)\) 的价值是\(A_{i,j}\)。
我们定义一条路径的价值是，这条路径经过的坐标的前 \(K\) 大的价值之和。
问：所有路径中，价值最小的路径，价值是多少?
$ 1 \leq H,W \leq 30 \(，\) 1 \leq K < H+W \(，\) 1 \leq A_{i,j} \leq 10^9 $。
Solution
设 \(f[i][j][c][w]\) 表示到 \((i, j)\) 时，路径上共有 \(c\) 个点被计入答案，且当前这前 \(c\) 大值的最小值为 \(w\) 的最小价值。
由于当前的数加进来后可能必须连带着将之前路径上的数也给加进来，因此这个 dp 有问题。
考虑枚举第 \(k\) 大值，这样就能确定当前数是否能加进答案。
设 \(f[i][j][c]\) 表示到 \((i, j)\) 时，路径上共有 \(c\) 个点被计入答案的最小价值。转移是容易的。
[ABC269G] Reversible Cards 2（2440）
Problem
有 \(n\) 张卡片，第 \(i\) 张卡片正面有数字 \(a_i\)，背面有数字 \(b_i\)，同时 \(\sum_{i=1}^n (a_i+b_i)=m\)。所有卡片起初均被正面朝上地放置。
对于 \(\forall k\in[0,m]\)，输出使得所有卡片朝上的数字之和为 \(k\) 时，需要翻面至少多少张卡片；如果不能通过翻面卡片使得所有卡片朝上的数字之和为 \(k\) 则输出 \(-1\)。
\(1\le n\le 2\times 10^5,0\le m\le 2\times 10^5,0\le a_i,b_i\le m\)。
Solution
[AGC062B] Split and Insert（2407）
Problem
现有一个 \(n\) 阶升序排列，要求你做 \(K\) 次操作达到一个给定的最终排列。定义第 \(i\) 次操作为：
- 任选一个数 \(x_i(0 \le x_i < n)\)，将当前排列的末 \(x_i\) 个数插到前 \(n - x_i\) 个数中，且这 \(x_i\) 个数的相对位置保持不变。
给定每次操作的权重 \(c_i\)，定义总代价为 \(\sum\limits_{i = 1}^{K}c_ix_i\)。求达到最终排列的最小代价，若无解则输出 \(-1\)。
$ 2 \leq N \leq 100 \(，\) 1 \leq K \leq 100 \(，\) 1 \leq C_i \leq 10^9 $。
Solution
正着做难以记录信息，考虑倒序 dp，即每次从排列中提取一段连续值域的上升子序列放到末尾，使整个排列升序。
为什么转化题意中的操作提出来的一定是连续值域：在原题意中，假设每次只拿一个数，则执行 \(n\) 次操作后必然能达到目标序列。因此原题意下每次只取未被取到的一段末尾必定能够达到最终序列，对应到转化后
对值域进行区间 dp，设计 \(f_{i, l, r}\) 表示进行到正序第 \(i\) 次操作，使得值域 \([l, r]\) 在排列中上升的最小代价。
初始化所有排好序的值域区间 \(l, r\) 为 \(f_{K + 1, l, r} = 0\)，其它区间 \(f_{K + 1, l, r} = \infin\)，答案为 \(f_{K, 1, n}\)，若其为 \(\infin\) 则输出 \(-1\)。
转移如下：
\[\begin{aligned} f_{i, l, r} &\xleftarrow{\min} f_{i + 1, l, r} \\ f_{i, l, r} &\xleftarrow{\min} f_{i + 1, l, k} + f_{i + 1, k + 1, r} + c_i \times (r - x) \end{aligned} \]时间复杂度 \(O(n^3k)\)。
[AGC032D] Rotation Sort（2602）
Problem
给定一个 \(n\) 阶排列， 你可以花费\(A\)使一个区间最左边的数跑到最右边， 或者花费\(B\)的代价使最右边到最左边， 求把整个序列变成升序的最少花费。\(1 \le n \le 5000, 1 \le A, B \le 10^9\)。
Solution
乐子题，但做不出来的人更乐子。
首先每个数最多被操作一次，因为你可以按一定顺序把它们全部往左放或全部往右放（这个说明并不严谨， 但是这个结论很好猜）。
其次不被操作的子序列一定是单增的，这个显然。
从前往后 dp，设计 \(f_{i, j}\) 表示考虑了前 \(i\) 个元素，最后一个没被操作的元素值为 \(j\) 的最小花费，转移时讨论当前的数是否被操作：
\[\begin{aligned} f_{i, j} &\xleftarrow{\min} f_{i - 1, j} + A, a_i > j \\ f_{i, j} &\xleftarrow{\min} f_{i - 1 ,j} + B, a_i < j \\ f_{i, a_i} &\xleftarrow{\min} f_{i - 1, k}, k < a_i \end{aligned} \]\(O(n^2)\)，但是可以线段树优化至 \(O(n\log{n})\)。最大的难点在于证明吧。
[ARC156D] Xor Sum 5（2568）
Problem
给定 \(n\) 个数的数列 \(a\) 和一个整数 \(k\)。对于所有长度为 \(k\)，值域为 \([1,n]\) 的数列 \(p\)，求出 \(\sum _{i=1}^{k} a_{p_i}\) 的异或和。
$ 1\ \leq\ N\ \leq\ 1000 \(，\) 1\ \leq\ K\ \leq\ 10^{12} \(，\) 0\ \leq\ A_i\ \leq\ 1000 $。
Solution
根据异或的性质，相同的两个数异或起来为 \(0\)，又可以观察到有很多数列本质相同，即 \(a\) 中的数出现次数是完全一致的，那么可以合在一起去算。
记 \(a_1, a_2, \dots, a_n\) 出现的次数分别为 \(c_1, c_2, \dots, c_n\)，则答案为：
\[\bigoplus\binom{k}{c_1, c_2, \dots, c_n}\sum\limits_{i = 1}^{n}a_ic_i \]多项式系数决定了后面的和式会不会对答案做出贡献。经典套路，用卢卡斯定理判断组合数的奇偶性，对于这个多项式，可以把它拆成 \(\binom{k}{c_1}\binom{k - c_1}{c_2}\dots\) 的形式，那么可以显然地发现当二进制下 \(c_1\) 是 \(k\) 的子集时，和式才有可能对答案做出贡献。类似地，也必须要求 \(c_2, c_3, \dots, c_n\) 都是 \(k\) 的子集才可能对答案做出贡献。于是我猜了个结论：\(c_1, c_2, \dots, c_n\) 均为 \(k\) 的子集与该和式对答案做贡献互为充要条件。但马上又否定了这个结论：例如 k = 111, c1 = 001, c2 = 001，\(\binom{k - c_1}{c_2}\) 是偶数，但是 \(c_1, c_2\) 又确实都是 \(k\) 的子集。不妨将这一连串二项式系数的乘积视作一个过程：首先 \(c_1\) 是 \(k\) 的子集，然后 \(k - c_1\)，\(c_1\) 占的一部分集合被去掉了；\(c_2\) 也要是 \(k\) 的子集，然后 \(k - c_1 - c_2\)，又去掉一部分集合。重复这个过程，易知 \(c_1, c_2, \dots, c_n\) 是两两不交的 \(k\) 的子集；又由于 \(\sum\limits_{i = 1}^{n}c_i = k\)，所以 \(c\) 序列在二进制下将 \(k\) 完全划分。这才是和式做贡献的充要条件。
Greedy Ant（2560）
Problem
\(n\) 个甜度不同糖果分别放在数轴上的 \(2, 4, \dots, 2n\) 上，Snuke 和蚂蚁轮流选择吃一个糖果，Snuke 先手。
Snuke 可以任取糖果，但蚂蚁只能从吃离它最近的糖果，若距离相同则选择甜度大的。
对每个蚂蚁的起始点 \(1, 3, \dots, 2n + 1\)，求 Snuke 能获得的最大甜度和。\(1 \le 400, 1 \le a_i \le 10^6\)。
Solution
这个范围非常区间 dp，但这个状态怕是不好想。
蚂蚁的策略非常简单，也非常配合我们做题：被吃掉的糖果正好是一段区间。
但 Snuke 很聪明，他可以任意选取，但区间的性质就被破坏了，我们就不方便区间 dp。
那么我们强行让 Snuke 降维成蚂蚁，让他也只能从被吃掉的糖果区间向两边选取。
但毕竟 Snuke 并不是蚂蚁，对于他曾经可以任选糖果的能力，我们将其视作 Snuke 可以囤操作次数，把功能转化为信息。
设计 \(f[l][r][k]\) 表示 \((l, r)\) 内的糖果已经吃完，Snuke 囤了 \(k\) 步操作次数，在取完所有糖果后 Snuke 可以获得的最大甜度和。
转移是容易的。
但蚂蚁是困难的，对于面前的庞然大物，沉思着谁才是真正的 Greedy Ant。
Balance and Coins
[ABC303G] Bags Game
Problem
Takahashi（先手）和 Aoki（后手）在玩游戏。他们有无限的钱，从左到右一共有 \(N\) 个物品，第 \(i\) 个价值 \(x_i\)，两个人轮流操作，每次轮到的一个人可以做 \(3\) 种操作之一（假设还剩下 \(n\) 个物品）。
- 拿走最左边或者最右边的物品。
- 付给 Snuke \(A\) 块钱，然后重复以下操作 \(\min(B,n)\) 次：拿走最左边或者最右边的物品。
- 付给 Snuke \(C\) 块钱，然后重复以下操作 \(\min(D,n)\) 次：拿走最左边或者最右边的物品。
定义一个人的最大收益是拿到的所有东西的价值之和减去付给 Snuke 的钱数。
请问如果 \(2\) 个人都使用最优策略，使得自身的收益减去对方的收益尽量的大，那么最终 Takahashi 的收益减去 Aoki 的收益会是多少？
- \(1\le B,D\le N\le 3000,A,C\le 10^9\)。
Solution
区间 dp。
一开始想的是记 \(f_{l, r, 0/1}\) 表示还剩 \([l, r]\) 内的数未取，上一步操作的人是先/后手的最大的答案，然后按区间长度从大到小转移。但这样做会把对手的所有可能的操作都转移过去，包括那些智障的操作，因此正着考虑不太好处理。
如果把过程倒着考虑，记录取区间 \([l, r]\) 的数时的价值，然后再向更大的区间转移，可以保证双方在任意时刻都是足够聪明的，即不论轮到哪一方走，总会使己方更优。
记 \(f_{l, r}\) 表示仅考虑 \([l, r]\) 内的数，区间内先手收益减去后手收益的最大值。
然后很容易得到 \(O(n^3)\) 的转移。code ABC303G \(O(n^{3})\)
转移的瓶颈在于要枚举子区间，我们发现需要枚举的子区间的长度在同一个询问区间时都是一样的（\(len - B\) 或 \(len - D\)），于是可以对每种长度的区间 \(f_{l, r} + s_r - s_{l - 1}\) 建立 ST 表，可以优化到 \(O(n^2\log{n})\)。code ABC303G \(O(n^{2}\log{n})\)
[ABC228H] Histogram
Problem
给定两个正整数序列 \(A\) 与 \(C\) , 你可以做任意次操作, 每次操作你可以花费 \(C_i\) 的代价给 \(A_i\) 加上 \(1\)。
设操作完后的序列 \(A\) 有 \(K\) 个不同的元素, 这会造成 \(K\times X\) 的代价, 其中 \(X\) 为给定常数。最小化总代价。
\(1 \le N \le 2 \times 10^5\)，\(1 \le X \le 10^6\)， \(1 \le A_i, C_i \le 10^6(1 \le i \le N)\)。
Solution
[AGC007D] Shik and Game
[AGC004E] Salvage Robots
[AGC040E] Prefix Suffix Addition
[ARC078F] Mole and Abandoned Mine
Problem
给一个 \(n\) 个点 \(m\) 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 \(1\) 到 \(n\) 只有 \(1\) 条不经过重复点的路径，问割掉的边权和最小是多少。
\(2 \le n \le 15, n - 1 \le m \le \frac{n(n - 1)}{2}\)。
Solution
\(n \le 15\)，点不能重复经过，都明显指向了状态压缩。
有一个非常显然的事情：\(1\) 到 \(n\) 的路径一定是一条链，并且在一个确定的图上，这条链是唯一的。
于是我们可以利用链的性质，将 “当前走到了链上的哪一个点” 记录在 dp 状态中。
然后再考虑链外的点，链外的点只会连接链上至多一个点。可以想象，最优图的形态一定是在链上连上若干个连通块，其中连通块内的点之间尽可能连边，同一个连通块内的点全部连向链上的同一个点（当然前提是连边在原图中出现）。
我们知道了连边的一些性质，不妨就先求出最大的边权和，再用总和减一下即可。
记 \(w1_{S, i}\) 表示点集 \(S\) 向点 \(i\) 连边的最大边权和，\(w2_{S}\) 表示点集 \(S\) 内部连边的最大边权和，\(w_{u, v}\) 表示点 \(u\) 和点 \(v\) 之间的边权。
设计 \(f_{S, i}\) 表示当前构建的图中包含的点集为 \(S\)，\(1\) 到 \(n\) 的路径已经走到了点 \(i\) 的最大边权和。讨论在点 \(i\) 处选择连向路径上的下一个点，或者是在该点处接上一个连通块：
- \(i \to j\)：\(i\) 走向路径上的下一个点 \(j\)，其中 \(j \not\in S\)：\(f_{S \cup j, j} \xleftarrow{\max} f_{S, i} + w_{i, j}\)。
- \(i \leftarrow T\)：点集 \(T\) 作为连通块连向点 \(i\)，其中 \(T \cap S = \emptyset\)：\(f_{S\cup T, i} \xleftarrow{\max} f_{S, i} + w1_{T, i} + w2_{T}\)。
Largest Smallest Cyclic Shift
[ABC221G] Jumping sequence
Problem
有一个无限大的平面直角坐标系，初始时你在 \((0,0)\) 处。给你一个长度为 \(n\) 的序列 \(d\)，你可以移动 \(n\) 步，每一步可以选择：
-
向上移动 \(d_i\) 距离，从 \((x,y)\) 到 \((x,y+d_i)\)
-
向下移动 \(d_i\) 距离，从 \((x,y)\) 到 \((x,y-d_i)\)
-
向右移动 \(d_i\) 距离，从 \((x,y)\) 到 \((x+d_i,y)\)
-
向左移动 \(d_i\) 距离，从 \((x,y)\) 到 \((x-d_i,y)\)
你想在 \(n\) 步结束后位于 \((A,B)\) 位置，问是否存在这样的方案，如果存在需输出任意一种方案。
\(1 \le n \le 2000\)，\(|A|, |B| \le 3.6\times 10^6\)，\(1 \le d_i \le 1800\)。
Solution
单独考察一维，这个问题就是个 01 背包。麻烦的是前后两维是绑定在一起的。
如何解除这种绑定？转切比雪夫距离！
\((A, B) \to (A + B, A - B)\)。
对应地，考察每一步的变化量也以同样的方式进行转化：
- \((0, d_i) \to (d_i, -d_i)\)
- \((0, -d_i) \to (-d_i, d_i)\)
- \((d_i, 0) \to (d_i, d_i)\)
- \((-d_i, 0) \to (-d_i, -d_i)\)
然后就可以分别考虑两个维度的背包问题了！
具体地，要求出一种分配正负号的方案，使 \(\pm{d_i} \pm{d_2} \pm \dots \pm{d_n} = A(\text{ or } B)\)。
考虑两边同时加上 \(\sum{d}\)，转化为对每个物品选或不选的问题，这样物品就会带上一个 \(2\) 倍的系数。
为了优化时空，可以采用 bitset 优化这种判断是否可以拼出一个数的背包问题。
很遗憾，如果只转化到了这一步，你会被出题人卡空间。你没有办法进行滚动优化，因为你需要根据之前的 dp 值倒推移动方案。
你发现如果 \(A (\text{ or } B) + \sum{d}\) 不能被 \(2\) 整除，那么一定无解，因为每个物品的权值都是 \(2\) 的倍数。
于是可以将左右同除 \(2\)，将空间砍掉一半，这样就能过了。
时空复杂度均为 \(O(\frac{n\sum{d}}{w})\)。
[ABC219H] Candles
Problem
\(N\) 支蜡烛放在无限延伸的数轴上。\(i\) 第一支蜡烛的坐标是 \(x_i\)，在 $0 $ 的时刻，蜡烛的长度是 $a_i $。点燃的蜡烛每 \(1\)，长度就短 \(1\)，当长度为 \(0\) 时，蜡烛就会燃烧殆尽，之后长度不变。另外，被熄灭的蜡烛的长度不变。
高桥君在 \(0\) 时刻坐标 \(0\)，每分钟可以移动不到 \(1\)。高桥君在与自己所在坐标相同的坐标上有蜡烛的情况下，能够将蜡烛的火熄灭。(同一坐标中有多个蜡烛的情况下可以一起吹灭)在这里，熄灭蜡烛所需的时间可以忽略不计。
请求出高桥采取适当行动时，从 \(0\) 到 $ 10^{100}$ 分钟之后剩下的蜡烛长度之和可能的最大值。
$ 1\ \leq\ N\ \leq\ 300 \(，\) -109 \leq X_i \leq 109 \(，\) 1\ \leq\ A_i\ \leq\ 10^9 $。
Solution
闲话：可能是 OI 生涯最神圣的一次了，考试的时候想 + 写用了 20min，没写对拍，竟然过了。
不过能做出来还是有一个很大原因的，那就是前一天做了 这个题。
首先离散化。
看到这个坐标轴上左右游走的模型，不难想到区间 dp。
由于需要知道移动的距离，则对于一个状态到另一个状态的转移，需要在状态中记录位置信息。幸运的是，这是好维护的：考虑走完 \([l, r]\)，则此时必然停在左端点处或右端点处。
记 \(f_{l, r, 0/1}\) 表示考虑完区间 \([l, r]\)，此时停在左/右端点的最大权值。
在转移时，考察当前蜡烛对权值的增量，发现需要知道停在此蜡烛时已经过去了多少时间。不幸的是，这实在是无法维护了。
我们先考虑弱化版问题，即蜡烛的长度可以为负数，并且要将所有蜡烛的最终长度计入贡献（即使是负数）。
问题出在蜡烛的减少量无法对每个蜡烛 独立 地进行贡献。那么就采用 整体思想，对于一次移动，发现所有区间外的蜡烛都会减少相同的长度，那么可以在这一步就将这些减少量全部减掉。这本质上是 费用提前计算 的思想。
回到本题，你不能直接将区间外的所有蜡烛都减去这一步走的代价，因为蜡烛的长度不能小于 \(0\)。但是蜡烛的长度等于 \(0\) 时，对答案没有任何贡献，于是可以把这种情况视作这根蜡烛根本就不存在，或者说你并没有选择这根蜡烛计入答案权值。于是一个新的信息呼之欲出：考虑完当前区间后，区间外的蜡烛中还要有多少个被你考虑在内。
记 \(f_{l, r, k, 0/1}\) 表示考虑完区间 \([l, r]\)，停在左/右端点，并且区间外还有 \(k\) 个被计入最终答案权值的蜡烛。
转移的时候枚举当前蜡烛是否被考虑计入答案权值，并只将 \(k\) 个蜡烛减去同一个代价，而不是将所有区间外的蜡烛都减去代价。这样总能保证在最优方案内，把那些讨厌的在移动过程中长度就已经变为 \(0\) 的蜡烛给排除在外。
濒死的红烛未知将来的灭亡，井底之蛙难观自己已陷得多深。诚然，人类并不生活在井里。可他们也曾试图钻入地心，试图认识邃蓝的海洋。而如今，他们甘愿用小男孩的眼泪将这片美丽禁锢，化作他们发光的钻石；黄土坡混杂着浑黑的石粒，黄沙漫天更有高高飘过的白云。
我们如何等待小男孩穿越井下的天空，烧尽泪水的最后一抹余晖。
[ABC262G] LIS with Stack
Problem
给定空序列 \(X\) 、空栈 \(S\) 和一个长度为 \(N\) 的序列 \(A=(a_1,a_2,\cdots,a_N)\) 。
从前往后考虑每一个 \(a_i, i = 1, 2, \dots, N\)，你可以选择将 \(a_i\) 插入 \(S\) 栈顶，或舍弃 \(a_i\)。
任意时刻，只要 \(S\) 不为空，你就可以选择把 \(S\) 的栈顶移动到 \(X\) 的尾处。
求出可能形成的所有 不降序列 \(X\) 中，\(X\) 长度的最大值。
\(N \le 50, \forall i \in [1, n], 1 \le a_i \le 50\)。
Solution
一道不算很难的区间 dp 好题 —— 同时对序列下标和元素值域进行区间 dp。
记 \(f_{i, j, l, r}\) 表示考虑 \(a_{i \dots j}\)，选取元素值域在 \([l, r]\) 内的数构成 \(X\) 时（此处及以下均默认 \(X\) 不降），\(X\) 长度的最大值。
考虑 \(a_i\) 如果加进 \(X\)，将以怎样的方式产生贡献：入栈后立即进入 \(X\)；先被挤到下面，之后再被弹出来。
- \(a_i\) 不入栈：\(f_{i, j, l, r} \xleftarrow{\max} f_{i + 1, j, l, r}\)。
- \(a_i\) 入栈后直接弹出：\(f_{i, j, l, r} \xleftarrow{\max} f_{i + 1, j, a_i, r} + 1\)。
- \(a_i\) 入栈后被暂时压在下面，在 \(a_k(i < k \le j)\) 时进行大清洗把 \(a_i\) 弹出：\(f_{i, j, l, r} \xleftarrow{\max} f_{i + 1, k, l, a_i} + f_{k + 1, j, a_i, r}\)。
状态数 \(O(n^4)\)，时间复杂度 \(O(n^5)\)。
[AGC033D] Complexity
Problem
- 给定一个 \(N\) 行 \(M\) 列的字符矩阵。
- 我们定义一个字符矩阵的凌乱度为：
- 若这个字符矩阵中所有字符都相同，则凌乱度为 \(0\)。
- 否则，则考虑所有的沿水平或者竖直方向的直线，将字符矩阵分成两个不为空的部分，设两个部分的凌乱度分别为 \(a\) 和 \(b\)，则整个字符矩阵的凌乱度为 \(\max(a,b)+1\) 的最小值。
- 请你求出，给出的字符矩阵的凌乱度是多少。
- \(1 \leq N, M \leq 185\)。
Solution
朴素的暴力：暴力记录 \(f_{i, j,k, l}\) 表示 \((i, j) \sim (k, l)\) 的矩阵的 Complexity，转移枚举分割线，时间复杂度 \(O(n^5)\)，空间复杂度 \(O(n^4)\)。
时间可以先放一放，我们需要先思考一个可行的做法使得空间复杂度不会爆炸。
可以考虑 交换 dp 状态与存储的信息，即将答案压进状态中，把之前状态中的某一维拎出来作为记录的信息。
同时发现，Complexity 的大小不超过 \(O(\log{n} + \log{m})\)，因为你可以总是将矩形从中间分开。
重新考虑 dp：记 \(f_{w, i, l, r}\) 表示矩形的 Complexity 不超过 \(w\)，左上角为 \((i, l)\)，右上角为 \((i ,r)\) 时，下边界行编号的最大值。
初始化 \(f_{0, i, l, r}\)，把同色矩形预处理出来。答案为满足 \(f_{w, 1, 1, m} = n\) 的最小 \(w\)。
- \(f_{w, i, l, r} \xleftarrow{\max} f_{w - 1, i, l, r}\)，显然。值得一提的是，\(\le w\) 的状态设计是 dp 中一种常见的优化转移的手段。
- 横着切一刀：\(f_{w, i, l, r} \xleftarrow{\max} f_{w - 1, f_{w - 1, i, l, r} + 1, l, r}\)。
- 竖着切一刀，只能枚举竖线的位置：\(f_{w, i, l, r} \xleftarrow{\max} \min(f_{w - 1, i, l, k}, f_{w - 1, i, k + 1, r})\)。
空间复杂度 \(O(nm^2(\log{n} + \log{m}))\)，时间复杂度 \(O(nm^3(\log{n} + \log{m}))\)。
如果不用记忆化搜索可以卡着过。注意输入 char 数组时空间不要抵着开。code AGC033D \(O(nm^3(\log{n} + \log{m}))\)
想办法优化掉枚举竖线的步骤。可以利用单调性，用指针维护出最优决策点。
具体地，在此题中，如果 \(w, i, l\) 固定，则当 \(r\) 增加时，能够决定 \(f_{w, i, l, r}\) 的竖线位置 \(k\) 单调不减。
由此可以做到 \(O(nm^2(\log{n} + \log{m}))\)。code AGC033D \(O(nm^2(\log{n} + \log{m}))\)
[ABC319F] Fighter Takahashi
Atcoder：[ABC319F] Fighter Takahashi
洛谷：[ABC319F] Fighter Takahashi
Problem
一棵以 \(1\) 为根的 \(n\) 个节点的树，一个 otto 位于 \(1\) 号节点，其初始能力值为 \(1\)。
其余的每个节点 \(i\)，用三元组 \((t_i, s_i, g_i)\) 表示其信息：
-
若 \(t_i = 1\)，则该节点上有一只虚空卡比兽，其生命值为 \(s_i\)，如果 otto 的能力值不小于 \(s_i\)，则 otto 可以选择击掰这只虚空卡比兽，并使 otto 的能力值加 \(g_i\)。
-
若 \(t_i = 2\)，则该节点上有一个韭菜盒子，能够使 otto 的能力值乘上 \(g_i\)，并保证给出的 \(s_i = 0\)。
节点可以重复经过。问 otto 能否到达所有节点。
\(1 \le n \le 500, 0 \le m \le 10\)。
Solution
我的翻译显然是在犯贱，还请各位去看原题面。
一个显然的贪心策略是：如果当前还有不用药水能够击败的敌人，那一定是优先击败这个敌人，而不是去吃药水。
考虑在使用一个药水之前所有能击败的敌人，很显然击败他们的顺序是无关紧要的。也就是说，如果确定了 \(m\) 个药水的使用顺序，则击败的结果是确定的。
当已知药水的使用顺序时，我们可以采用 bfs 的思想，用优先队列决定当前能走到的未击败的敌人中生命值最低的是哪一个。
如果当前没有可以击败的敌人了，那就以确定的顺序服用一瓶药水，然后继续跑 bfs。
这样做的时间复杂度为 \(O(m!\times n\log{n})\)，数量级高达 \(10^{10}\)。
套路地，我们可以用状压 dp 优化枚举排列。记 \(f_S\) 表示已使用的药水集合为 \(S\) 时，能力值的最大值以及对应的遍历情况（具体即记哪些点已经被遍历。能这样做的正确性保证在于，如果 \(S\) 和能力值是确定的，则遍历情况也是确定的）。枚举下一个使用的药水是哪一个，实际上就是在逐步确定药水的使用顺序，但由于状压优化，那些不优的顺序在确定顺序的过程中就已经被 pass 掉了，不会在之后的转移中出现。
状态数 \(O(2^m)\)，枚举下一个药水 \(O(m)\)，转移 \(O(n\log{n})\)，总时间复杂度 \(O(nm2^m\log{n})\)。
注意能力值可能很大，但我们只需要将其与 \(10^9\) 取最小值，使其仍然能击败敌人即可。
这确实是一道有一定码量的 dp 好题。
[ABC320F] Fuel Round Trip
Problem
とてもたのしいカードゲーム
Problem
有 \(N\) 张扑克堆成一个栈，从上往下第 \(i\) 张花色是 \(C_i\)，点数是 \(A_i\)，价值是 \(V_i\)。有这样一个操作，每次可以选择拿走从上往下第 \(1\) 张或者第 \(3\) 张，拿走的牌必须和上一次拿走的花色或者点数一样。请问如何拿牌，才能使得拿出来的牌的价值和最大。
\(1 \le N \le 500\)。
Solution
赛时笔记。
以下按照栈顶到栈底给牌编号为 \(1 \sim n\)。
然后模拟一下发现了以下事情：
-
在编号最大的被拿走的牌之前，至多只有两张牌未被拿走。
-
拿走从上往下第 \(3\) 张牌后，在编号最大的被拿走的牌之前，恰好有两张牌未被拿走。
感觉很可以 dp 啊！
称在编号最大的被拿走的牌之前未被拿走的牌为空位。
存在以下转移：
- 两个空位变一个空位
- 一个空位变没有空位
- 一个空位变两个空位
- 没有空位变两个空位
记 \(f_{i, j, k}\) 表示 \(i\) 作为在编号最大的被拿走的牌，之前存在两个空位 \(j, k(j < k)\) 的最大价值。
记 \(g_{i, j, k}\) 表示 \(i\) 作为在编号最大的被拿走的牌，最后一张被拿走的牌是 \(j\)，存在的空位是 \(k\)。如果空位不存在则 \(k = 0\)。
这个状态很妙啊！完全依靠了我们所发掘出来的性质：如果剩两个空位，则必然最后一个选择的牌就是编号最大的被拿走的牌，即 \(i\)；否则我们无法确定最后一个选择的牌是谁，但是此时多出来的空余的状态，因此把最后一个选择的牌记录到这个空位上。
另一个角度来讲，\(f\) 记录的是拿走从上往下第 \(3\) 张牌后的状态，\(g\) 记录的是拿走从上往下第 \(1\) 张牌后的状态。
写一下 dp 转移：（下记 \(V(x, y)\) 表示 \(x, y\) 在花色或点数上至少有一个相同）
\[\begin{aligned} g_{i, j, k} &\xleftarrow{\max} f_{i, j, k} + w_{j}, V(i, j) \\ g_{i, k, 0} &\xleftarrow{\max} g_{i, j, k} + w_{k}, V(j, k) \\ g_{i, i, 0} &\xleftarrow{\max} g_{i - 1, j, 0} + w_{i}, V(j, i) \\ f_{i, j, k} &\xleftarrow{\max} f_{i - 1, j, k} + w_{i}, V(i - 1, i) \\ f_{i, k, i - 1} &\xleftarrow{\max} g_{i - 2, j, k} + w_{i}, V(j, i) \\ f_{i, i - 2, i - 1} &\xleftarrow{\max} g_{i - 3, j, 0} + w_{i}, V(j, i) \\ \end{aligned} \]由此可见，应先更新 \(f\) 值，再更新 \(g\) 值。
前三个数的 dp 值可以手算出来，避免之后的 dp 过程繁琐的特判。
时空复杂度均为 \(O(n^3)\)。空间要算好！这个可是 \(10^8\) 级别的。我趣，有点危险啊:(
upd：这个可以滚动数组的。
[ABC201F] Insertion Sort
Problem
\(N\) 个人排成一列，他们的编号是 \(1\) 到 \(N\) 的排列。左起第 \(i\) 个人的编号是 \(P_i\)。
你可以以任意次序进行任意多次下列操作：
- 选择一个人，设其编号为 \(i\)，支付 \(A_i\) 的代价将其移动到任意位置。
- 选择一个人，设其编号为 \(i\)，支付 \(B_i\) 的代价将其移动到最左端。
- 选择一个人，设其编号为 \(i\)，支付 \(C_i\) 的代价将其移动到最右端。
其中 \(A_i,B_i,C_i\) 由题目输入。
你的目标是使得所有人的编号从左至右递增。输出达成目标的最小代价。
\(1 \le N \le 2 \times 10^5\)。
[ARC056C] 部門分け
Problem
高桥君在一个有 \(N\)人组成的公司中。给定任意两个员工 \(i\) 和 \(j\) 之间的信赖度 \(w(i,j)\) 和一个正整数 \(K\)。将 \(N\) 人分成了几个部门，并规定权值为 \((\text{部门的数目})\times K -(\text{属于不同部门的2个人之间的信赖度的总和})\)。求权值的最大值。
\(1 \le N \le 17\)。
Solution
记 \(f_{S}\) 表示考虑点集 \(S\) 的权值最大值。
\[\begin{aligned} f_{S \cup T} \xleftarrow{\max} f_{S} + K - cost \\ \end{aligned} \]这里 \(cost\) 表示点集 \(T\) 与 \(S\) 产生的信赖度总和。
预处理 \(s_{i, S} = \sum\limits_{j \in S}w_{i, j}\)，可以做到 \(O(n3^{n})\)。code ARC056C - \(O(n3^{n})\)
实际上这样达到了 \(10^9\) 量级，非常危险。
考虑 容斥 计算 \(cost\)，记 \(c_{S}\) 表示点集 \(S\) 与其外部点产生的信赖度总和，则 \(cost = \frac{c_{T} - c_{S \cup T} + c_{S}}{2}\)。
这样可以做到 \(O(n^{2}\times 2^{n})\) 预处理 \(c\)，\(O(3^{n})\) 进行 DP。code ARC056C - \(O(n^{2}2^{n} + 3^{n})\)
[ABC176F] Brave CHAIN
Problem
hhoppitree 有 \(3n\) 张卡片，其中每张卡片上都写着 \(1\sim n\) 中的一个数，他会重复以下操作 \(n-1\) 次：
- 将最左侧的 \(5\) 张牌任意排列，排列后，删去最左侧的 \(3\) 张牌，如果这三张牌上写着同样的数，hhoppitree 可以获得 \(1\) 分。
最后，如果剩余的 \(3\) 张牌上的数字一样，那么他还可以额外得到 \(1\) 分。
现在，hhoppitree 想要知道，他得到的分数最高是多少。
\(1 \le N \le 2000\)，\(1 \le A_{i} \le N\)。
Solution
有一个显然的 \(O(n^3)\) DP，记 \(f_{i, x, y}\) 表示进行了 \(i\) 次操作，剩余序列的左起第一个元素为 \(x\)、第二个元素为 \(y\) 的最大分数。之所以能这样记是因为第 \(i\) 次操作后被影响的是一段 确定 的前缀，即每次操作会影响到 \(3\) 个 确定 的元素，因此只需记录由之前操作剩下的 \(2\) 个元素即可知道当前操作需要执行的 \(5\) 个元素是什么。
由于枚举状态的时间复杂度就达到了 \(O(n^3)\)，因此我们不能枚举所有状态。由于 \(f_{i, x, y}\) 对于 \((x, y)\) 关于 \(i\) 单调不降，因此可以考虑采取滚动数组转移，转移时只需枚举需要被更新的状态。
考虑给这个 DP 加上一些策略来优化它，比如这个贪心策略：如果当前操作的牌中存在三张相同数字的牌，那么直接打出计入分数。还是容易猜到的。
我们需要一个把策略套进 DP 转移中的方式。由于我们已经知道了每次操作中的其中 \(3\) 个数，我们可以根据这三个数的值去辅助 DP 转移，换句话说，我们可以用这三个确定的元素去 限制被更新的 DP 状态在一个可以接受的枚举范围内。
下面开始转移。
考虑使用 “满三加一” 的策略：
-
若三个数相同：\(f_{i, x, y} \xleftarrow{\max} f_{i - 1, x, y} + 1\)。由于不能枚举所有状态，因此这里可以将 \(+1\) 直接计入最终的答案，而 \(f_{i, x, y}\) 保持不变。
注意：此时需要立即下一步操作，因为这里视作强行将这三张牌打出，不能进行其它操作。
-
若两个数相同，记 \(p\) 为相同的数，\(q\) 为另一个，则：\(f_{i, x, q} / f_{i, q, x} \xleftarrow{\max} \max(f_{i - 1, p, x} + f_{i - 1, x, p}) + 1\)。枚举 \(x\)，更新 \(O(n)\)。
-
记这三个数分别为 \(p, q, r\)，则：\(f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} f_{i - 1, p, p} + 1\)，对 \(q, r\) 也同理更新，\(O(1)\)。
注意：该更新对存在两个数相同的情况也要进行！！！（问题在于对单独的那一个数进行处理）
考虑重排对 DP 值的影响。记三个数为 \(p, q, r\)。
- 把之前剩下的两个数全部打出，则：\(f_{i, p, q} / f_{i, q, p} / f_{i, p, r} / f_{i, r, p} / f_{i, q, r} / f_{i, r, q} \xleftarrow{\max} \max\limits_{1 \le x, y \le n} (f_{i - 1, x, y}, f_{i - 1, y, x})\)。由于 \(\max\) 值可以随更新时动态维护，因此不用枚举 \(x, y\)，仍然是 \(O(1)\) 更新。
- 在剩下的两个数中保留一个，则：\(f_{i, x, p} / f_{i, p, x} / f_{i, x, q} / f_{i, q, x} / f_{i, x, r} / f_{i, r, x} \xleftarrow{\max} \max\limits_{1 \le y \le n}(f_{i - 1, x, y}, f_{i - 1, y, x})\)。同理，对每个 \(x\) 实时维护 \(\max\) 值，实现 \(O(n)\) 更新。
- 将新来的三个数 \(p, q, r\) 全部打出，但这种情况已经被 “满三加一” 的讨论中考虑过了，因此避开了 \(O(n^2)\) 更新。
实现上，可以用 vector 存哪些状态在当轮被更新。
于是总时间复杂度为 \(O(n^2)\)，令人感动。调得令人感动。code ABC176F
[ARC066E] Addition and Subtraction Hard
Problem
给你一个只包含'+'、'-'、正整数的式子，你需要在式子中添加一些括号，使运算结果最大，输出最大的结果。
\(1 \le N \le 10^5\)，\(1 \le A_i \le 10^9\)。