简介面向信息学奥赛选手的2024年CSP-S第二轮上机真题PDF适合备战CCF非专业级软件能力认证提高级、需要按正式赛题训练算法设计与代码实现的中学生及教练使用。压缩包内共1个PDF文件约210KB完整收录决斗、超速检测、染色、擂台游戏四道传统题的题目描述、输入输出格式、样例解释与数据范围并附文件命名、main函数返回值、源文件大小、栈空间、编译选项及评测机配置等注意事项。已有5869人学习可借此熟悉提高级赛题的命题风格、限时与内存约束围绕图论、贪心、模拟、搜索与动态规划等考点逐题梳理解题思路并用样例和附加测试自测代码、查漏补缺。1. 从“想出来”到“写对”之间隔着一层翻译2024年CSP-S第二轮的四道题难的不是知识点是把过程翻译成结构的那个瞬间。提高级的信息学奥赛考到今天排序、二分、贪心、树形 DP 这些名词选手都背得出来真正卡人的是题目给你一段连续发生的物理过程或游戏过程你得在十几分钟内看出它等价于一个静态的组合对象——一个最大重数、一个区间集合、一个只跟末尾位置有关的 DP 状态、一棵按轮次分层的二叉树。决斗、超速检测、染色、擂台游戏四道题题干风格差得很远落点却出奇一致。看懂这种翻译是怎么发生的比多刷十道原题有用。2. 决斗为什么答案只是出现次数最多的那个值先给结论这道题的答案就是数组 $r$ 里出现次数最多的那个值的出现次数也就是 $\max_v \text{cnt}[v]$。样例 1 里1 2 3 1 21 出现两次、2 出现两次、3 出现一次答案是 2样例 2 里 136 出现八次答案是 8。两行代码能过。但为什么是它值得掰开。2.1 把“攻击顺序”画成图它其实是一组链每回合让怪兽 $i$ 打怪兽 $j$只有 $r_i r_j$ 时 $j$ 才会退出。把“$i$ 打过 $j$”画成一条有向边 $i \to j$立刻得到两条硬约束一只怪兽最多发起一次攻击所以每个点出度不超过 1一只怪兽被打死就退出不会再挨第二次打所以每个点入度也不超过 1。出度、入度都不超过 1 的图只能是一堆互不相交的链和环。环不可能出现。边的方向严格跟着能力值下降$r_i r_j$沿着边走数值一路变小走不回起点。所以整张图就是一组合法的链每条链形如 $r_{a_1} r_{a_2} \cdots r_{a_k}$。一条链上最后剩谁执行顺序是从链尾往前打$a_{k-1}$ 打 $a_k$$a_{k-2}$ 打 $a_{k-1}$一直到 $a_1$ 打 $a_2$。每一步攻击者都还在场上被打死的立刻退出打完一轮只剩链头 $a_1$。链头自己攻击过一次它打了 $a_2$满足“游戏结束时未退出的怪兽都已发起过攻击”这个终止条件。所以一条 $k$ 个点的链净存活 1 只总存活数恰好等于链的条数。问题于是变成把这个数组划分成尽量少的严格递减链。2.2 下界和构造为什么最少链数恰好等于最大重数下界很直接值相同的两只怪兽之间不可能有边$r_i r_j$ 不成立$r_i r_j$ 时防御也打不破所以任意两只同值怪兽必定落在不同的链里。若某个值出现了 $c$ 次链数至少是 $c$。取出现次数最多的那个值链数下界就是 $\max_v \text{cnt}[v]$。上界靠构造而且构造思路朴素得让人意外。把所有值从大到小处理同一批同值的怪兽各自接到一条现有链的尾部要求是链尾的值严格大于它如果现有链不够分就新开链。同值的怪兽之间不能串在一条链上所以每个值的 $\text{cnt}[v]$ 只必须占用 $\text{cnt}[v]$ 条不同的链。初始时最大值的那批怪兽各开一条链链数就是最大值出现的次数等于 $\max_v \text{cnt}[v]$而这个数永远不小于任何其他值的出现次数所以后面每一批都能找到足够多的不同链来接接上去之后链尾的值变成当前值仍然严格递减。链数始终不增长构造成功。最少链数 最大重数两边的界合上了。这套论证其实就是 Dilworth 定理在这个偏序上的具体形态最小链划分等于最长反链而这里的反链就是“值相同的一整组”。提示别被“最优攻击顺序”这几个字带偏去搜博弈或者状压。一旦把攻击关系看成出度入度受限的图顺序的维度就消失了只剩链的条数。2.3 代码只有六行但两处边界容易翻车#include cstdio #include algorithm const int MAXR 100005; int cnt[MAXR]; int main() { int n; scanf(%d, n); int answer 0; for (int i 0; i n; i) { int r; scanf(%d, r); // 攻击力与防御力是同一个 r answer std::max(answer, cnt[r]); } printf(%d\n, answer); return 0; }参数说明$r \le 10^5$直接开桶空间 400KB 出头时间 $O(n \max r)$。如果值域更大就换成排序后统计连续段时间不变空间降到 $O(n)$。第一处边界是 $n 1$。只有一只怪兽它没有“另一只怪兽”可打游戏直接结束存活 1 只最大重数也是 1对得上。第二处是同值互殴。$r_i r_j$ 时攻击力等于对方防御力“小于等于防御力则无事发生”所以杀不掉这正是不等式取严格大于的原因——代码里没有这个判断是因为结论已经把相等的情况吸收掉了。血泪经验是有人把判定写成去推链推出来的构造在等值数据上全线崩塌。3. 超速检测把物理题翻译成区间覆盖再翻译成选点贪心这道题有两问所有测速仪全开时被抓到的车辆数以及在不漏掉任何超速车辆的前提下最多能关掉几个测速仪。第一问看着像模拟第二问看着像搜索实际上从头到尾只做了一件事——把每辆车翻译成一段测速仪下标区间然后做一次区间选点。3.1 一辆车被哪些测速仪抓到本质是一个连续区间车从 $d$ 驶入初速度 $v$加速度 $a$位置 $p$ 处的瞬时速度满足 $u(p) v^2 2a(p - d)$这是提示里给的位移—速度公式。超速的判定是 $u(p) V^2$。关键在这个式子的单调性。$a 0$ 时 $u(p)$ 随 $p$ 严格递增超速的测速仪位置构成一个后缀$a 0$ 时随 $p$ 严格递减构成一个前缀$a 0$ 时 $u(p)$ 恒等于 $v^2$要么全抓要么全不抓。三种情况合起来任意一辆车被抓到的测速仪集合永远是测速仪数组上一个连续的区间 $[lo, hi]$。还有一个细节让这件事更干净$a 0$ 时车会在速度降到 0 时驶离主干道但不用专门去算停车点。位置超过停车点时 $v^2 2a(p-d)$ 直接变成负数跟 $V^2 \ge 1$ 比较必然不成立判定函数自动为假。所以只要把测速仪位置限制在 $[d, L]$ 里二分就能用。3.2 不开根号用整数比较换掉浮点精度朴素做法是对每个测速仪算 $\sqrt{v^2 2a(p-d)}$ 再和 $V$ 比这是典型的精度翻车现场。题目提示里专门点了一句“如果你使用浮点数进行计算需要注意潜在的精度问题”通常意味着出题人手上就有卡精度的数据。比较 $u(p) V^2$ 和比较 $\sqrt{u(p)} V$ 完全等价而前者全程整数。值域估算一下$v \le 10^3$ 所以 $v^2 \le 10^6$$|a| \le 10^3$$|p - d| \le 10^6$所以 $|2a(p-d)| \le 2 \times 10^9$。全部在 32 位有符号范围内都不会溢出但保险起见用long long。typedef long long ll; // 判定车在位置 pos 处是否超速。a 可正可负直接算速度平方不开根号 inline bool overspeed(ll d, ll v, ll a, ll pos, ll V) { return v * v 2 * a * (pos - d) V * V; }有了单调性就不需要逐辆车扫描所有测速仪直接在有序的测速仪数组上二分$a 0$ 二分出第一个超速的位置$a 0$ 二分出最后一个超速的位置$a 0$ 单独判一次。// 返回这辆车被抓到的测速仪下标区间 [lo, hi]空区间用 lo hi 表示 std::pairint, int catchRange(const Car c, const std::vectorll p, ll L, ll V) { int lo std::lower_bound(p.begin(), p.end(), c.d) - p.begin(); // 车不会经过 d 之前的测速仪 int hi std::upper_bound(p.begin(), p.end(), L) - p.begin() - 1; // 也不会经过 L 之后的 if (lo hi) return {1, 0}; if (c.a 0) // 匀速要么全抓要么都不抓 return c.v V ? std::make_pair(lo, hi) : std::make_pair(1, 0); if (c.a 0) { // 加速超速的是一个后缀 int l lo, r hi, first hi 1; while (l r) { int mid (l r) 1; if (overspeed(c.d, c.v, c.a, p[mid], V)) first mid, r mid - 1; else l mid 1; } return {first, hi}; } else { // 减速超速的是一个前缀 int l lo, r hi, last lo - 1; while (l r) { int mid (l r) 1; if (overspeed(c.d, c.v, c.a, p[mid], V)) last mid, l mid 1; else r mid - 1; } return {lo, last}; } }参数说明c.d / c.v / c.a分别是驶入位置、初速度、加速度p是升序的测速仪位置数组L是路段长度V是限速。返回值是闭区间的下标对。整段的时间是每辆车 $O(\log m)$总复杂度 $O(n \log m)$$n, m \le 10^5$ 时在 2.0 秒里非常宽裕。3.3 区间选点为什么按右端点排序是对的把每辆超速车辆对应的区间收集起来第二问就变成了一个经典问题从 $m$ 个测速仪里选尽量少的点使每个区间至少包含一个点答案再用 $m$ 减去选点数。贪心策略是按右端点升序排序依次判断当前区间的左端点是否已经大于上次选中的点若是则新选一个点位置取当前区间的右端点。正确的直觉是这样所有区间里右端点最靠左的那个它必须被某个点覆盖而任何覆盖它的点都不可能比它的右端点更靠右地“顺带”覆盖更多区间——因为其他区间的右端点都在它右边。把点放在这个右端点上能覆盖的区间集合是包含关系下的最大集不会错过更优解。反过来按左端点排序就翻车左端点最靠左的区间可能极其长选中它并不能保证后面短区间被覆盖。// seg 里是每辆超速车的 [lo, hi]均为测速仪下标 std::sort(seg.begin(), seg.end(), [](const std::pairint,int x, const std::pairint,int y) { return x.second y.second; // 按右端点升序 }); int used 0, last -1; // last 是上一次选中的测速仪下标 for (const auto s : seg) { if (s.first last) { // 当前点覆盖不到这个区间 used; last s.second; // 新点放在区间右端点 } } // 第一问答案 seg.size()第二问答案 m - used注意last初始化为-1因为测速仪下标从 0 开始s.first last在第一次一定成立。区间数量最多 $n$ 个排序 $O(n \log n)$扫描 $O(n)$。这套“先转区间、再贪心”的流程是这类题最常见的实现思路。踩过的坑在于有人把测速仪位置当作连续坐标去做实数区间合并结果边界上差一个位置就错。测速仪是离散的所有区间端点必须是下标不能是浮点位置。4. 染色与擂台游戏两套题为什么都在“只记边界”染色和擂台游戏放在一起看表面上一个是数组染色、一个是二叉树晋级八竿子打不着。但它们的暴力解都是 $O(n^2)$ 级别而正解都在做同一件事证明“两两之间的关系”可以被压缩成“只跟边界有关”的少量状态。4.1 染色状态里真正有用的只有两个末尾位置染色题的得分规则很怪$A_i$ 的贡献取决于它左侧最近的同色数相等才得分否则为 0。这意味着一个位置能不能得分只跟它所在颜色的“最后一个位置”有关跟更早的历史毫无关系。于是状态可以这么定$f[i][j]$ 表示前 $i$ 个数已经染完其中一种颜色的最后一个位置是 $i$另一种颜色的最后一个位置是 $j$$j i$时的最大得分。为什么只需要记两个位置因为处理到 $i1$ 时它要么接在颜色 $i$ 后面要么接在颜色 $j$ 后面两者各自查一次相等就能算出增量再往前的信息全被 $f[i][j]$ 这个数吸收掉了。转移只有两条// f[i][j]: 前 i 个元素已染色一种颜色的末尾在 i另一种颜色的末尾在 j 时的最大得分 // 转移一把 A[i1] 染成和 A[i] 相同的颜色 // f[i1][j] max(f[i1][j], f[i][j] (A[i1] A[i] ? A[i1] : 0)) // 转移二把 A[i1] 染成和 A[j] 相同的颜色 // f[i1][i] max(f[i1][i], f[i][j] (A[i1] A[j] ? A[i1] : 0))状态数是 $O(n^2)$$n 2 \times 10^5$本文还有配套的精品资源点击获取
简介面向信息学奥赛选手的2024年CSP-S第二轮上机真题PDF适合备战CCF非专业级软件能力认证提高级、需要按正式赛题训练算法设计与代码实现的中学生及教练使用。压缩包内共1个PDF文件约210KB完整收录决斗、超速检测、染色、擂台游戏四道传统题的题目描述、输入输出格式、样例解释与数据范围并附文件命名、main函数返回值、源文件大小、栈空间、编译选项及评测机配置等注意事项。已有5869人学习可借此熟悉提高级赛题的命题风格、限时与内存约束围绕图论、贪心、模拟、搜索与动态规划等考点逐题梳理解题思路并用样例和附加测试自测代码、查漏补缺。1. 从“想出来”到“写对”之间隔着一层翻译2024年CSP-S第二轮的四道题难的不是知识点是把过程翻译成结构的那个瞬间。提高级的信息学奥赛考到今天排序、二分、贪心、树形 DP 这些名词选手都背得出来真正卡人的是题目给你一段连续发生的物理过程或游戏过程你得在十几分钟内看出它等价于一个静态的组合对象——一个最大重数、一个区间集合、一个只跟末尾位置有关的 DP 状态、一棵按轮次分层的二叉树。决斗、超速检测、染色、擂台游戏四道题题干风格差得很远落点却出奇一致。看懂这种翻译是怎么发生的比多刷十道原题有用。2. 决斗为什么答案只是出现次数最多的那个值先给结论这道题的答案就是数组 $r$ 里出现次数最多的那个值的出现次数也就是 $\max_v \text{cnt}[v]$。样例 1 里1 2 3 1 21 出现两次、2 出现两次、3 出现一次答案是 2样例 2 里 136 出现八次答案是 8。两行代码能过。但为什么是它值得掰开。2.1 把“攻击顺序”画成图它其实是一组链每回合让怪兽 $i$ 打怪兽 $j$只有 $r_i r_j$ 时 $j$ 才会退出。把“$i$ 打过 $j$”画成一条有向边 $i \to j$立刻得到两条硬约束一只怪兽最多发起一次攻击所以每个点出度不超过 1一只怪兽被打死就退出不会再挨第二次打所以每个点入度也不超过 1。出度、入度都不超过 1 的图只能是一堆互不相交的链和环。环不可能出现。边的方向严格跟着能力值下降$r_i r_j$沿着边走数值一路变小走不回起点。所以整张图就是一组合法的链每条链形如 $r_{a_1} r_{a_2} \cdots r_{a_k}$。一条链上最后剩谁执行顺序是从链尾往前打$a_{k-1}$ 打 $a_k$$a_{k-2}$ 打 $a_{k-1}$一直到 $a_1$ 打 $a_2$。每一步攻击者都还在场上被打死的立刻退出打完一轮只剩链头 $a_1$。链头自己攻击过一次它打了 $a_2$满足“游戏结束时未退出的怪兽都已发起过攻击”这个终止条件。所以一条 $k$ 个点的链净存活 1 只总存活数恰好等于链的条数。问题于是变成把这个数组划分成尽量少的严格递减链。2.2 下界和构造为什么最少链数恰好等于最大重数下界很直接值相同的两只怪兽之间不可能有边$r_i r_j$ 不成立$r_i r_j$ 时防御也打不破所以任意两只同值怪兽必定落在不同的链里。若某个值出现了 $c$ 次链数至少是 $c$。取出现次数最多的那个值链数下界就是 $\max_v \text{cnt}[v]$。上界靠构造而且构造思路朴素得让人意外。把所有值从大到小处理同一批同值的怪兽各自接到一条现有链的尾部要求是链尾的值严格大于它如果现有链不够分就新开链。同值的怪兽之间不能串在一条链上所以每个值的 $\text{cnt}[v]$ 只必须占用 $\text{cnt}[v]$ 条不同的链。初始时最大值的那批怪兽各开一条链链数就是最大值出现的次数等于 $\max_v \text{cnt}[v]$而这个数永远不小于任何其他值的出现次数所以后面每一批都能找到足够多的不同链来接接上去之后链尾的值变成当前值仍然严格递减。链数始终不增长构造成功。最少链数 最大重数两边的界合上了。这套论证其实就是 Dilworth 定理在这个偏序上的具体形态最小链划分等于最长反链而这里的反链就是“值相同的一整组”。提示别被“最优攻击顺序”这几个字带偏去搜博弈或者状压。一旦把攻击关系看成出度入度受限的图顺序的维度就消失了只剩链的条数。2.3 代码只有六行但两处边界容易翻车#include cstdio #include algorithm const int MAXR 100005; int cnt[MAXR]; int main() { int n; scanf(%d, n); int answer 0; for (int i 0; i n; i) { int r; scanf(%d, r); // 攻击力与防御力是同一个 r answer std::max(answer, cnt[r]); } printf(%d\n, answer); return 0; }参数说明$r \le 10^5$直接开桶空间 400KB 出头时间 $O(n \max r)$。如果值域更大就换成排序后统计连续段时间不变空间降到 $O(n)$。第一处边界是 $n 1$。只有一只怪兽它没有“另一只怪兽”可打游戏直接结束存活 1 只最大重数也是 1对得上。第二处是同值互殴。$r_i r_j$ 时攻击力等于对方防御力“小于等于防御力则无事发生”所以杀不掉这正是不等式取严格大于的原因——代码里没有这个判断是因为结论已经把相等的情况吸收掉了。血泪经验是有人把判定写成去推链推出来的构造在等值数据上全线崩塌。3. 超速检测把物理题翻译成区间覆盖再翻译成选点贪心这道题有两问所有测速仪全开时被抓到的车辆数以及在不漏掉任何超速车辆的前提下最多能关掉几个测速仪。第一问看着像模拟第二问看着像搜索实际上从头到尾只做了一件事——把每辆车翻译成一段测速仪下标区间然后做一次区间选点。3.1 一辆车被哪些测速仪抓到本质是一个连续区间车从 $d$ 驶入初速度 $v$加速度 $a$位置 $p$ 处的瞬时速度满足 $u(p) v^2 2a(p - d)$这是提示里给的位移—速度公式。超速的判定是 $u(p) V^2$。关键在这个式子的单调性。$a 0$ 时 $u(p)$ 随 $p$ 严格递增超速的测速仪位置构成一个后缀$a 0$ 时随 $p$ 严格递减构成一个前缀$a 0$ 时 $u(p)$ 恒等于 $v^2$要么全抓要么全不抓。三种情况合起来任意一辆车被抓到的测速仪集合永远是测速仪数组上一个连续的区间 $[lo, hi]$。还有一个细节让这件事更干净$a 0$ 时车会在速度降到 0 时驶离主干道但不用专门去算停车点。位置超过停车点时 $v^2 2a(p-d)$ 直接变成负数跟 $V^2 \ge 1$ 比较必然不成立判定函数自动为假。所以只要把测速仪位置限制在 $[d, L]$ 里二分就能用。3.2 不开根号用整数比较换掉浮点精度朴素做法是对每个测速仪算 $\sqrt{v^2 2a(p-d)}$ 再和 $V$ 比这是典型的精度翻车现场。题目提示里专门点了一句“如果你使用浮点数进行计算需要注意潜在的精度问题”通常意味着出题人手上就有卡精度的数据。比较 $u(p) V^2$ 和比较 $\sqrt{u(p)} V$ 完全等价而前者全程整数。值域估算一下$v \le 10^3$ 所以 $v^2 \le 10^6$$|a| \le 10^3$$|p - d| \le 10^6$所以 $|2a(p-d)| \le 2 \times 10^9$。全部在 32 位有符号范围内都不会溢出但保险起见用long long。typedef long long ll; // 判定车在位置 pos 处是否超速。a 可正可负直接算速度平方不开根号 inline bool overspeed(ll d, ll v, ll a, ll pos, ll V) { return v * v 2 * a * (pos - d) V * V; }有了单调性就不需要逐辆车扫描所有测速仪直接在有序的测速仪数组上二分$a 0$ 二分出第一个超速的位置$a 0$ 二分出最后一个超速的位置$a 0$ 单独判一次。// 返回这辆车被抓到的测速仪下标区间 [lo, hi]空区间用 lo hi 表示 std::pairint, int catchRange(const Car c, const std::vectorll p, ll L, ll V) { int lo std::lower_bound(p.begin(), p.end(), c.d) - p.begin(); // 车不会经过 d 之前的测速仪 int hi std::upper_bound(p.begin(), p.end(), L) - p.begin() - 1; // 也不会经过 L 之后的 if (lo hi) return {1, 0}; if (c.a 0) // 匀速要么全抓要么都不抓 return c.v V ? std::make_pair(lo, hi) : std::make_pair(1, 0); if (c.a 0) { // 加速超速的是一个后缀 int l lo, r hi, first hi 1; while (l r) { int mid (l r) 1; if (overspeed(c.d, c.v, c.a, p[mid], V)) first mid, r mid - 1; else l mid 1; } return {first, hi}; } else { // 减速超速的是一个前缀 int l lo, r hi, last lo - 1; while (l r) { int mid (l r) 1; if (overspeed(c.d, c.v, c.a, p[mid], V)) last mid, l mid 1; else r mid - 1; } return {lo, last}; } }参数说明c.d / c.v / c.a分别是驶入位置、初速度、加速度p是升序的测速仪位置数组L是路段长度V是限速。返回值是闭区间的下标对。整段的时间是每辆车 $O(\log m)$总复杂度 $O(n \log m)$$n, m \le 10^5$ 时在 2.0 秒里非常宽裕。3.3 区间选点为什么按右端点排序是对的把每辆超速车辆对应的区间收集起来第二问就变成了一个经典问题从 $m$ 个测速仪里选尽量少的点使每个区间至少包含一个点答案再用 $m$ 减去选点数。贪心策略是按右端点升序排序依次判断当前区间的左端点是否已经大于上次选中的点若是则新选一个点位置取当前区间的右端点。正确的直觉是这样所有区间里右端点最靠左的那个它必须被某个点覆盖而任何覆盖它的点都不可能比它的右端点更靠右地“顺带”覆盖更多区间——因为其他区间的右端点都在它右边。把点放在这个右端点上能覆盖的区间集合是包含关系下的最大集不会错过更优解。反过来按左端点排序就翻车左端点最靠左的区间可能极其长选中它并不能保证后面短区间被覆盖。// seg 里是每辆超速车的 [lo, hi]均为测速仪下标 std::sort(seg.begin(), seg.end(), [](const std::pairint,int x, const std::pairint,int y) { return x.second y.second; // 按右端点升序 }); int used 0, last -1; // last 是上一次选中的测速仪下标 for (const auto s : seg) { if (s.first last) { // 当前点覆盖不到这个区间 used; last s.second; // 新点放在区间右端点 } } // 第一问答案 seg.size()第二问答案 m - used注意last初始化为-1因为测速仪下标从 0 开始s.first last在第一次一定成立。区间数量最多 $n$ 个排序 $O(n \log n)$扫描 $O(n)$。这套“先转区间、再贪心”的流程是这类题最常见的实现思路。踩过的坑在于有人把测速仪位置当作连续坐标去做实数区间合并结果边界上差一个位置就错。测速仪是离散的所有区间端点必须是下标不能是浮点位置。4. 染色与擂台游戏两套题为什么都在“只记边界”染色和擂台游戏放在一起看表面上一个是数组染色、一个是二叉树晋级八竿子打不着。但它们的暴力解都是 $O(n^2)$ 级别而正解都在做同一件事证明“两两之间的关系”可以被压缩成“只跟边界有关”的少量状态。4.1 染色状态里真正有用的只有两个末尾位置染色题的得分规则很怪$A_i$ 的贡献取决于它左侧最近的同色数相等才得分否则为 0。这意味着一个位置能不能得分只跟它所在颜色的“最后一个位置”有关跟更早的历史毫无关系。于是状态可以这么定$f[i][j]$ 表示前 $i$ 个数已经染完其中一种颜色的最后一个位置是 $i$另一种颜色的最后一个位置是 $j$$j i$时的最大得分。为什么只需要记两个位置因为处理到 $i1$ 时它要么接在颜色 $i$ 后面要么接在颜色 $j$ 后面两者各自查一次相等就能算出增量再往前的信息全被 $f[i][j]$ 这个数吸收掉了。转移只有两条// f[i][j]: 前 i 个元素已染色一种颜色的末尾在 i另一种颜色的末尾在 j 时的最大得分 // 转移一把 A[i1] 染成和 A[i] 相同的颜色 // f[i1][j] max(f[i1][j], f[i][j] (A[i1] A[i] ? A[i1] : 0)) // 转移二把 A[i1] 染成和 A[j] 相同的颜色 // f[i1][i] max(f[i1][i], f[i][j] (A[i1] A[j] ? A[i1] : 0))状态数是 $O(n^2)$$n 2 \times 10^5$本文还有配套的精品资源点击获取
