AGC016F Games on DAG

给定一张 $n$ 个点 $m$ 条边的 DAG，求 $2^m$ 个边的子集中有多少个构成的子图满足 $\operatorname{SG}(1)\not =\operatorname{SG}(2)$。

$1\leq n\leq 15$。

用 $2^m$ 减去 SG 值相同的方案数，不妨记 $f_S$ 表示点集 $\{1,2\}\in S$ 中满足要求的边集的数量，进行一个子集的 dp。

为了正确转移，我们把考虑边的选取顺序为，当前有点集 $T$，然后新加入 SG 值为 $0$ 的点集 $U$，并且 $U$ 中没有边，$T$ 中每个点至少连向一个 $U$ 中的点，记这样的方案数为 $c(T,U)$，这个可以每个点独立计算，则 $T$ 中点的 SG 值均加一，即按照 SG 值分层转移，保证 $1,2$ 的 SG 值相等。

考虑枚举 $S$ 的子集 $T$ 进行转移，$U=\complement_ST$，即把 $S$ 分割为 $T$ 再加上 SG 值为 $0$ 的 $U$，初始状态为 $f_S=1$，即选择边集为空，转移为：

• $\{1,2\}\in T$，则贡献 $f_T\times c(T,U)$ 到 $f_S$ 上；
• $\{1,2\}\in U$，则贡献 $g_T\times c(T,U)$ 到 $f_S$ 上，其中 $g_T$ 是 $T$ 中任意连边的方案数，此时 $1,2$ 都是新加入的 SG 值为 $0$ 的点，前面点的 SG 值无关紧要。

因为 $n$ 很小，所以可以位运算方便地预处理并计算贡献。

时间复杂度 $O(n\times 3^n)$，一份参考代码实现。

CF868F Yet Another Minimization Problem

给定序列 $a_{1\cdots n}$，将其划分为 $k$ 个子段，一个子段 $[l,r]$ 的代价 $c(l,r)$ 为 $l\leq i<j\leq r,a_i=a_j$ 的 $(i,j)$ 的数量，最小化所有子段的代价和。

$2\leq n\leq 10^5$，$2\leq k\leq 20$，$1\leq a_i\leq n$。

考虑题意为转移 $f_i=\min_{i'<i}\{f_{i'}+c(i'+1,i)\}$ 做 $k$ 次，即 $f_{i,j}$ 为前 $i$ 个恰好分成 $j$ 段的答案压掉了 $j$ 一维。

因为复杂度不太能做，我们挖掘一下性质考虑优化，若 $i_1<i_2$，它们的转移点为 $i'_1,i'_2$，则有 $i'_1\leq i'_2$，即满足决策单调性，证明如下：

假设存在 $i_1<i_2,i'_1>i'_2$，则由于 $i'_1,i'_2$ 是决策点，有 $f_{i'_1}+c(i'_1+1,i_1)\leq f_{i'_2}+c(i'_2+1,i_1)$ 以及 $f_{i'_2}+c(i'_2+1,i_2)\leq f_{i'_1}+c(i'_1+1,i_2)$。我们将其相加再抵消掉两边的 $f$，为了简洁省略掉 $c$，得到 $(i'_1,i_1)+(i'_2+1,i_2)\leq (i'_2+1,i_1)+(i'_1+1,i_2)$，看着有点抽象，不妨画个图：

下面的图示的点分别表示上面四个端点中间的三段，边表示计算连接的两个点之间的贡献，不难发现 $1$ 是大于等于 $2$ 而不是小于等于，因为其边集包含了 $2$ 的边集，故决策单调性成立。

于是进行一个分治 $\operatorname{solve}(l,r,ql,qr)$ 表示 $[l,r]$ 的决策点在 $[ql,qr]$ 中，计算出 $mid=\lfloor\frac{l+r}2\rfloor$ 位置的决策点 $qmid$ 后递归 $\operatorname{solve}(l,mid-1,ql,qmid),\operatorname{solve}(mid+1,r,qmid,qr)$，问题来到了如何计算 $qmid$。普通的题目在这里是暴力枚举 $[ql,qr]$ 找到决策点，但这题由于要计算 $c$，所以考虑用类似莫队的思想来完成这个过程，维护全局指针 $[L,R]$ 表示当前得到了 $c(L,R)$，每次要计算时暴力挪动端点，考虑这样移动端点的次数，从父节点的 $[ql,qr]$ 到 $[ql,qmid]$ 的移动或逆向进行至多是 $O(qr-ql)$ 的，每个区间的 $qr-ql$ 求和的级别是 $O(n\log n)$ 的，因为无论怎么切割，一层的总数是 $O(n)$，共 $O(\log n)$ 层分治；在每个分治区间中的挪动也至多是 $O(qr-ql)$ 的，故端点移动次数为 $O(n\log n)$，单次移动复杂度是 $O(1)$，于是在这里使用莫队的思想复杂度是正确的。

因为要做 $k$ 次，总复杂度 $O(kn\log n)$，一份参考代码实现。

P5336 THUSC2016 成绩单

给定序列 $w_{1\cdots n}$，删除一个区间的代价是 $A+B\times (\max-\min)^2$，其中 $\max,\min$ 分别是区间中的最大值，最小值，删除后两边将会拼起来，求删完所有数的最小总代价。

$1\leq n\leq 50$，$1\leq w_i\leq 10^3$。

区间 dp，设 $g_{l,r}$ 为删完 $[l,r]$ 的最小总花费，但信息不足以转移，于是设 $f_{l,r,a,b}$ 表示区间 $[l,r]$ 的最小最大值为 $a,b$ 时的最小代价，$g_{l,r}=\min_{a,b}\{f_{l,r,a,b}+A+B\times (b-a)^2\}$，则从 $[l,r]$ 到 $[l,r+1]$ 的转移有：

• 啥都不干，直接往后推，$f_{l,r,a,b}\to f_{l,r+1,\min(a,w_{r+1}),\max(b,w_{r+1})}$；
• 保留 $a,b$，枚举 $k$ 把 $[r+1,k]$ 给删掉，$f_{l,r,a,b}+g_{r+1,k}\to f_{l,k,a,b}$，但由于在转移时直接照写会出现 $g_{r+1,k}$ 未求出的问题，改为 $f_{l,k,a,b}+g_{k+1,r}\to f_{l,r,a,b}$。

于是直接枚举 len 转移即可，实现时注意离散化，时间复杂度 $O(n^5)$，一份参考代码实现。