RainAir
My OI Blog
RainAir
「JZOJ6281」串

题目链接

题意

给你一个大串 $A$ 和若干小串 $B_i$,你可以做 $k$ 次操作:每次你可以选择从大串中删除一个小串,要求最后剩下的串尽量小,并输出长度
$lenA \leq 200,lenB_i \leq 10,m \leq 20$

题解

感觉自己做过 可惜不会做
首先我们考虑我们可以将删除操作变成删除在原串上的一段区间内和其匹配的字符串,我们考虑这种删除操作区间只可能不交或包含。不交的情况可以变成包含的情况(延长其中一个区间)
首先考虑如果能无限删除 那么就可以设 $f_{i,j}$ 表示是否能将 $[i,j]$ 区间内的串删完。考虑到之前的性质,我们有必要设 $g_{l,r,i,j}$ 表示区间 $[l,r]$ 能否被删成第 $i$ 个串的前 $j$ 个。
按照定义有 $g_{i,j,k,len_k} \to f_{i,j}$,我们只需要考虑 $j$ 怎么转移。
我们可以考虑 $r$ 这个字母是在哪里。
第一种情况:我们可以继续匹配一位,即
$$g_{l,r,i,j} = g_{l,r-1,i,j-1}$$
前提是 $B[i][j] = A[r]$
第二种情况:我们可以考虑将这个 $r$ 删除掉,即
$$g_{l,r,i,j} = g_{l,k,i,j} \& f_{k+1,r}$$
最后设 $h_i$ 表示前 $i$ 个的答案,可以直接递推:
$$h_i = \min_{j \leq i,f_{i,j} = 1} h_j + 1$$

那么现在加入了限制,我们可以考虑让 $f,g$ 都变成达到这种状态的最小步数,然后 $h$ 多加一维记录下现在操作了几次就好了。

总结

看完题解感觉就是个暴力 dp。。这种区间之间关系的题目如果有了一些性质(不存在相交,一个点最多被覆盖 x 次)之类的东西就可以很好 dp 了(可以少记很多东西)
并且还要注意这些操作的本质。。首先 $f$ 肯定很好想到的(毕竟你要求这个),但是删除的时候相当于好多段拼起来。。。所以我们需要记录对于每一个串,它匹配到了多少。大概这个思路吧
还是自己太菜了,NOIP T2 都不会,什么时候才能会这种题

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/942
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「JZOJ6281」串
题目链接 题意 给你一个大串 $A$ 和若干小串 $B_i$,你可以做 $k$ 次操作:每次你可以选择从大串中删除一个小串,要求最后剩下的串尽量小,并输出长度 $lenA \leq 200,lenB_i \leq 10,m…
扫描二维码继续阅读
2019-11-02
标签
近期评论