题解：P11782 [JOIGST 2024] 卡牌游戏 / Card Game 3

Solution首先考虑没有不同色的限制怎么做，显然就是让 $i$ 选择点数最大的卡牌，$j$ 选所有其他的卡牌，如果 $a_i + a_j > 0$ 就加上这个贡献。加上限制之后，和最大卡牌异色的我们可以用上面的方法处理。考虑和最大卡牌同色的卡牌怎么办？选择和最大卡牌异色的最大的卡牌，让 $i$ 选它，$j$ 选所有和最大卡牌同色的卡牌即可。Code#include<bits/...

atcoder dp contest

感觉该学点基础了。E考虑状态换维。J合并无用状态。发现只需要关心不同寿司个数的盘子的数量，所以设 $f[a][b][c]$ 表示当前还剩下 $a/b/c/(n - a- b - c)$ 盘有 $0/1/2/3$ 个寿司。O设 $f_S$ 表示前 $k$ 个男人和包含在 $S(|S| =k)$ 中的女人配对的方案数，枚举和第 $k$ 个男人匹配的女人转移。R基本套路：$A$ 为邻接矩阵，求出...

dp trick 之「连续段插入 dp」

模拟赛 T2 遇到的。对这类问题，一般会按值大小插入以消除后效性，先只在每段内考虑限制，再在两个段合并时考虑限制。P5999题意转化为求有多少个 $1 \sim n$ 的排列 $p$ 满足 $p_i$ 两边的数字同时大于或同时小于 $p_i$，且 $p_1 = s, p_n = t$。设 $f_{i, j}$ 表示前 $i$ 个数，分成 $j$ 段的方案数。从小到大加入每个数，对于 $i \...

题解：CF675E Trains and Statistic

首先考虑，对于点 $i$，如果要到达一个一步到不了的点，应该怎么走。显然，应该从 $i$ 到一个中转点，再往后走。考虑中转点应该怎么取，贪心的，我们让中转点取 $[i + 1, a_i]$ 中 $a_p$ 最大的点 $p$，因为 $p$ 的右端点最靠右，可以到达更多的点。考虑令 $f_i = \sum_{j = i + 1} ^ {n} \rho_{i, j}$，答案就是 $\sum f_i...