本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-21 21:59:36

原题单

剩余题单（包括课后题）

拜谢杨爹/bx/bx/bx

背包 DP

J - Cow Exhibition G

考虑把 $S,F$ 中的一种看作费用，另一种看作收益，把所有值加个常数变成非负，转化为 $01$ 背包求解，最后找到两种值都非负的最大值即可。

数位 DP

K - windy 数

用 dfs，由高位到低位填，参数为填到的位数 $x$，是否贴上界，是否有前导 $0$，上一位是 $last$，判断是否能填时要么有前导 $0$，要么跟上一位差的绝对值满足要求。加上没有前导 $0$ 且不贴上界时对于 $(x,last)$ 的解个数可以优化时间复杂度。

话说学长说更建议用递推写，感觉递推式子就是 $(x,last)$ 的数组，还没有了解过。

L - 01串 Stringsobits

求符合条件的第 $k$ 小数，考虑二分或倍增。这里二分一个数 $x$，求 $[0,x]$ 中符合条件的数个数 $s$，以 $s\ge k$ 来 check。求数的个数用数位 DP，参数里加入还能填的 $1$ 的个数即可，初始为 $(n,L,1)$。

N - Making Shapes

Too Hard. 大体是把每个向量选择的次数和各种和全都变成二进制进行数位 DP。

单调队列优化 DP

I - Mowing the Lawn G

不能安排连续超过 $K$ 只奶牛，考虑转化成找出若干只奶牛不安排，也就是选出的任意两只奶牛之间距离不能超过 $K+1$。设 $f_i$ 表示前 $i$ 只奶牛选出的最小效率和，则 $f_i=\min_{j=i-(k+1)}^{i-1}f_j+E_i$。

发现一定会用 $f_j$ 合法的最小值更新，所以若 $x<y$ 且 $f_x\ge f_y$，$x$ 一定永远不优于 $y$，用双端队列维护单调队列，每次从队首弹出过期元素，从队尾弹出不优的元素，保证队内的 $f_i$ 单调递减，每次用队首来转移即可。

M - PTA-Little Bird

设 $f_i$ 为跳到 $i$ 所需的最小代价，则 $f_i=\min_{j=i-k}^{i-1}f_j+[d_i\ge d_j]$，考虑用单调队列，需要判断两个点的优劣。发现 $f_x<f_y$ 时 $x$ 一定更优，若 $f_x=f_y$， 则 $d_x>d_y$ 时 $x$ 一定更优。因为每次的代价仅为 $1$，所以这样是对的。把 $(f_i,d_i,i)$ 放入单调队列，用队首更新即可。

树形 DP

E - Centroids

先找出重心，原重心一定合法。以重心 $g$ 为根计算每个点的子树大小。若 ${siz}_x=\frac n2$，可以直接把这颗子树拆下来，把剩余的 $\frac n2$ 接到指定的根上，保证会成为重心。所以 $x$ 子树内的点均合法。

对于其他点，断开自己子树显然是不合法的，那么只能断开 $g$ 其他子树中 $siz$ 最大的 $k$，且直接接到 $x$ 上。那么 $siz_x,siz_k$ 均小于 $\frac n2$，只要 $n-siz_x-siz_j\le\frac n2$ 即合法。预处理一下 $g$ 子树的前缀后缀 $siz$ 最大值，求子树 $m$ 时用前缀和后缀的最大值作为 $siz_k$ 即可。

G - 树上染色

考虑把贡献拆到边上，并在从子树合并到父节点时考虑进去。所以若子树 $v$ 中有 $j$ 个黑点，贡献的次数为 $S=j(k-j)+(siz_v-j)(n-siz_v-(k-j))$。合并入父节点时，转移为 $f_{u,i}=\min_{j=0}^{{siz}v} f{u,i-j}+f_{v,j}+Sw$。

注意外层 $i$ 逆序枚举以保证 $01$ 背包的性质，内层枚举顺序无所谓，但是一定要在开始时处理 $j=0$，也就是直接把这个子树中纯白的情况考虑进去了，否则在后面会直接加上 $Sw$ 导致算重。

C - 小 N 的独立集

考虑最朴素的算法，$2^n$ 枚举每个点的取值，然后直接 $O(n)$ 跑树上最大独立集，设 $f_{u,0/1}$ 表示 $u$ 不选/选时，$u$ 子树内的最大收益。接着考虑 DP 套 DP，把 $f$ 设入状态，设 $g_{u,v_0,v_1}$ 为以 $u$ 为根的子树中 $u$ 不选时最大值为 $v_0$，选时最大值为 $v_1$ 的方案数，更新时用 $g_{v,p,q}$ 更新 $g_{u,i+\max(p,q),j+p}=g_{u,i+\max(p,q),j+p}+g_{v,p,q}\times g_{u,i,j}$。

但是这样复杂度为 $O(n^4k^4)$，无法通过，考虑把后两维修改压一下，变成 $g_{u,v_0,v_1}$ 表示强制不选 $u$ 时最大为 $v_0$，不强制时最大为 $v_1$。可以发现 $v_1-v_0\le w_u\le k$，所以改为 $g_{u,v_0,d}$ 表示强制不选 $u$ 时最大为 $v_0$，不强制时最大为 $v_0+d$，转移时 $g_{u,i+p+q,\max(i+p+q,i+j+p)-(i+p+q)}$ 加上 $g_{u,i,j}\times g_{v,p,q}$，时间复杂度 $O(n^2k^4)$

H - 船往低处流

Too Hard. 好像是各种换根分讨，感觉很麻烦。

斜率优化

D - 序列分割

首先注意到确定分割位置后，无论分割顺序怎样，最终的结果相同，因为每个元素都会与所有与其所在部分不同的元素相乘。所以设 $f_{i,j}$ 表示考虑到前 $i$ 个元素，分了 $j$ 块的最大得分，有 $f_{i,j}=\max_{k=j-1}^{i-1}f_{k,j-1}+s_k(s_i-s_k)$，其中 $s$ 是 $a$ 的前缀和数组。

把 $j$ 维滚动掉，拆开这个式子，得到 $f_{i}=\max_{k=1}^{i-1}f_{k}+s_ks_i-s_k^2)$，即 $-s_is_k+f_i=f_k-s_k^2$，把 $-s_i$ 看作 $k$，$s_k$ 看作 $x$，$f_i$ 看作 $b$，$f_k-s_k^2$ 看作 $y$，就是 $kx+b=y$ 的形式。相当于拿着斜率为 $-s_i$ 的直线在第一象限扫，扫到最高的经过某一点 $(s_k,f_k-s_k^2)$ 时为最大截距 $f_i$。

所以按照 $(s_k,f_k-s_k^2)$ 维护一个上凸包，也就是斜率递减的折线。每次找到最后一条斜率大于目前 $-s_i$ 的线段，最优决策点即为这条线段后面的端点，可以二分。但是由于 $-s_i$ 递减，也就是所用直线的斜率递减，所以说决策点不会前移，用双端队列同时一直在队头弹出无用的点，每次的决策点就是队头了。

A - Yet Another Partiton Problem

Too Hard. 分治 + 斜率优化，还是太困难了。

决策单调性

F - Dispatch Money

Too Hard. 分治 + 决策单调性，还是太困难了。

其他 Trick

B - 经营与开发

发现每次相当于给答案加一个值 $x_i$ 并使后面的答案乘一个值 $y_i$，若 $type=1$，则 $x_i=a_iw,y_i=(1-0.01k)$，否则 $x_i=-b_iw,y_i=(1+0.01c)$，发现按顺序枚举会有后效性，考虑倒序处理，每次相当于乘上 $y_i$ 并加上 $x_i$，由于其他影响本处操作的操作在前面，所以后效性没了，求出最后答案乘上原始的 $w$ 即可。

O - 管道取珠

发现 $a_i^2$ 相当于操作两轮且序列相同的方案数，所以设 $f_{i,j,k}$ 表示两轮都操作了 $i$ 次，第一轮在上管取了 $j$ 个，第二轮在上管取了 $k$ 个，且操作序列相同的方案数。则转移有：

• $j>0,k>0,a_j=a_k$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j-1,k-1}$。
• $j>0,a_j=b_{i-k}$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j-1,k}$。
• $k>0,b_{i-j}=a_k$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j,k-1}$。
• $b_{i-j}=b_{i-k}$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j,k}$。

答案即为 $f_{n+m,n,n}$。