LJC讲dp

sdfzoj contest2 但当我用上了换行

给 $n$ 个长 $T$ 模式串, 含能匹配任何一个字符的通配符, 求有多少个字符串 $S$ 能匹配其中恰好 $k$ 个模式串. $n\le15, \vert T \vert \le50$

首先考虑了一个容斥做法, 算能匹配每一个模式串子集的方案数再容斥就结束了.

不过还有个DP, 如果设 $f_{i, S}$ 表示考虑前 $i$ 位能匹配集合 $S$ 的方案数, 转移就是枚举这一位填谁, 然后根据这个算能满足哪些模式串, 复杂度应该是 $O(26\times2^n \vert S \vert n)$ , 但是很容易发现卡不满, 据说实际上跑的飞快.

感觉这个dp做法的对所有串同时考虑的想法还挺不错?

sdfzoj contest0 T1

给一个数列 $A$ , 若一个位置为 $-1$ 表示你可以随便填, 求最长上升子序列长度. $n\le 10^6$

先给每个位置减去它的下标, 就可以是求最长不降子序列了, 考虑此时我们可以任意在两个元素间插入一个-1, 所以直接不带-1求最长不降子序列然后加上-1的个数. 这是对的吗?

然而是不对的, 这个每个位置减下标的结论只对整个序列才管用, 正确的做法是每个位置减去前面的-1的个数, 因为必然存在一个最优解使用了所有-1, 那么我们就强制不能把-1挤掉, 也就是选数的时候相邻两数之差大于等于之间-1个数, 这么做就过了.

P7961 [NOIP2021] 数列

给定整数 $n, m, k$ 和一个长度为 $m+1$ 的正整数数组 $v0, v1, …, vm$ .

对于一个长度为 $n$ , 下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 ${ai}$ , 我们定义它的权值为 $va1 \times va2 \times ⋯ \times van$ .

当这样的序列 ${a_i}$ 满足整数 $S=2^{a_1}+2^{a_2}+⋯+2^{a_n}$ 的二进制表示中 1 的个数不超过 $k$ 时, 我们认为 ${a_i}$ 是一个合法序列.

计算所有合法序列 ${a_i}$ 的权值和对 $998244353$ 取模的结果.

由于是二进制使得我们倾向于按二进制从低位向高位选, 也就相当于我们把 $a$ 按值域顺序考虑, 那么可以把题目做一个转化, 变成我们有长 $m$ 的序列中选长 $n$ 的下标序列, 那么考虑设 $f_{i, j, x, y}$ 表示已经考虑到二进制的第 $i$ 位, 已经选了 $j$ 个, 二进制下前面有 $x$ 个1, 同时这一位上积累的进位是 $y$ , 这里 $y$ 不一定是1, 也可能积累了一堆, 总之是留着后面进位的. 那么转移就是我们枚举选的最后一个:

$$
f_{i, j, k, l}\times \binom {m-j}{o}\times v_i^o\to f_{i-1, j-o, k+l\mathrm{and}1, o+\frac{l}{2}}
$$

就做完了

spoj19. [sdfzoj contest #2]我仿佛

给 $m$ 个区间, 让每个区间里有切仅有一个关键点, 最大化关键点个数.

序列上这类选点问题常常设 $f_i$ 表示强制选 $i$ 的情况下的答案, 那么考虑 $f_i$ 可以从哪里转移过来, 当前到 $i$ 的情况下, 一个区间 $[l, r]$ 共有3类:

  • 不包含 $i$ 且在右边, 显然不用管

  • 包含 $i$ , 那么转移过来的位置显然要满足 $j<l$

  • 不包含 $i$ 且在左边, 要求满足 $j\ge l$ ,

对于第二个限制, 要求覆盖每个位置的区间的最左的左端点, 可以线段树区间取min解决.

对于第三个限制, 要求右端点小于 $i$ 的左端点最大值, 把它按 $r$ 排序, 每次加入小于 $i$ 的, 扫着维护就行了.

P7962 [NOIP2021] 方差

给一个序列, 你可以进行任意多次让 $a_i=a_{i+1}+a_{i-1}-a_i$ , 最小化数组方差.

$n\le 400, a_i\le 600$ 或 $n\le 10^4, a_i\le 50$

首先这个操作相当于交换相邻两项差分, 那么也就是我们可以任意重排差分数组.

经过一番玄学发现方差数组是单谷的. 感性理解就是平均值一定是值域中间的, 那么你希望更多的数接近平均值, 所以就中间小两边大. 那么从小到大加入方差时就是选择每次加到头上或尾巴上.

众所周知

$$
n^2s^2=
n\sum a_i^2-(\sum a_i)^2
$$

我们很难直接维护这个两项相减的东西, 所以把一个记录到状态里, 设 $f_{i, j}$ 表示加入前 $i$ 个差分而和为 $j$ 的情况, 再设 $s_i=\sum_j^i d_j$ 为这一项的大小, 此时有两种转移:

  • 新数加到前面: $f_{i-1, j}+2xd_i+id_i^2\to f_{i, j+i\times d_i}$

  • 新数加到后面 $f_{i-1, j}+s_i^2\to f_{i, j+s_i}$

然后现在得到一个 $n^2a$ 的解法, 考虑 $n$ 很大时序列中很多都是0, 因为序列是不降的所以0一定在中间, 那么只要把0都跳过去就成了 $na^2$ .

P2569 [SCOI2010]股票交易

最近 $\text{lxhgww}$ 又迷上了投资股票, 通过一段时间的观察和学习, 他总结出了股票行情的一些规律.

通过一段时间的观察, $\text{lxhgww}$ 预测到了未来 $T$ 天内某只股票的走势, 第 $i$ 天的股票买入价为每股 $AP_i$ , 第 $i$ 天的股票卖出价为每股 $BP_i$ (数据保证对于每个 $i$ , 都有 $AP_i \geq BP_i$ ), 但是每天不能无限制地交易, 于是股票交易所规定第 $i$ 天的一次买入至多只能购买 $AS_i$ 股, 一次卖出至多只能卖出 $BS_i$ 股.

另外, 股票交易所还制定了两个规定. 为了避免大家疯狂交易, 股票交易所规定在两次交易(某一天的买入或者卖出均算是一次交易)之间, 至少要间隔 $W$ 天, 也就是说如果在第 $i$ 天发生了交易, 那么从第 $i+1$ 天到第 $i+W$ 天, 均不能发生交易. 同时, 为了避免垄断, 股票交易所还规定在任何时间, 一个人的手里的股票数不能超过 $\text{MaxP}$ .

在第 $1$ 天之前, $\text{lxhgww}$ 手里有一大笔钱(可以认为钱的数目无限), 但是没有任何股票, 当然, $T$ 天以后, $\text{lxhgww}$ 想要赚到最多的钱, 聪明的程序员们, 你们能帮助他吗?

对于 $100%$ 的数据, $0\leq W<T\leq 2000, 1\leq\text{MaxP}\leq2000$

对于所有的数据, $1\leq BP_i\leq AP_i\leq 1000, 1\leq AS_i, BS_i\leq\text{MaxP}$

容易想到设 $f_{i, j}$ 表示到第 $i$ 天有 $j$ 股时最大收益. 转移:

  • 从这一天第一次买入这么多: $f_{i, j}=-AP_i\times j$

  • 这一天什么也没干: $f_{i, j}=f_{i-1, j}$

  • 买进了一些 $f_{i, j}=f_{i-w-1, j-k}-k\times AP_i\ s. t. \ 0<k\le \min(j, AS_i)$

  • 买出了一些 $f_{i, j}=f_{i-w-1, j+k}+k\times BP_i\ s. t. \ 0<k\le min(BS_i, MaxP-j)$

由于有第二个的转移所以我们可以只从 $i-w-1$ 天转移过来而不用再枚举哪一天.

然后这样复杂度三次方, 可以通过单调队列优化成二次方.

P8352 [SDOI/SXOI2022] 小 N 的独立集

给一棵树, 对每个 $v\in [0, nk]$ 计数 $n$ 个点每个点点权在 $[1, k]$ 之间的最大独立集为 $v$ 的方案数.

$n\le 1000, k\le 5$

由于一个广为人知的求最大独立集的dp, 让我们想到设 $f_{u, i, j}$ 表示对于 $u$ 的子树, 选了的最大独立集为 $i$ , 不选为 $j$ 的方案数.

直接数状态数的话 $i, j\le nk$ , 总状态数是 $n^3k^4$ 的, 但是可以分析 $j\le i\le j+k$

  • $i\le j+k$ 是因为根本不会有这个样的合法状况, 如果不选 $u$ 的时候最大为 $j$ 那么加上 $u$ 一定不会增加超过 $k$ .

  • $i\ge j$ 是因为若 $i< j$ 那么最大独立集一定和 $i$ 没关系, 因为不选的限制显然是弱于选的限制的, 那么可以把所有这些压到一起处理.

状态数成 $n^2k^2$ 了

然后再有个优化, 直接转移的话式子显然是

$$
f_{v, x, y}f_{u, i, j}\to f_{u, i+y, j+\max(x, y)}
$$

复杂度 $n^4k^4$ , 但实际上我们的 $j, y$ 可以只枚举到 $k$ 倍对应子树大小, 看起来这个优化是玄学的, 但实际上可以分析: 记 $u$ 子树大小为 $siz_u$ , 此时我们合并一个子树到 $u$ 的复杂度为 $siz_v\times(siz_u-siz_v)\times k^2$ , 相当于一个点在 $v$ 内, 一个点在 $v$ 外的点对数量, 所以我们的复杂度可以类比过来, 考虑我们以后就再也不会枚举到 $u$ 子树内两个点的点对了, 那么每个点对只在他们的 lca 处被计算了一次, 点对个数是 $n^2$ 的, 所以总复杂度是 $n^2k^2$ 的啊.

然后就过了.