【BZOJ 3864】Hero meet devil

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3864
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/4799463.html
神犇题解Ⅱ:http://blog.csdn.net/popoqqq/article/details/46826271
神犇题解Ⅲ:http://blog.csdn.net/u011542204/article/details/51674319

解题报告

一开始一眼看成了“最长公共子串”
居然心里在嘲讽 $ WJMZBMR$ 也有naive的时候

先考虑一个这样的状态:$f[i][j][k]$ 表示文本串匹配到第$i$位、模式串匹配到第$j$位、最长公共子序列长度为$k$个时的方案数
但这样直接转移是错误的,因为这会使第三维的$k$意义变为:“最长公共子序列长度至少为$k$”。比如下面这个例子:

文本串:$azbzcz$
模式串:$abcd$
现在考虑在文本串末尾加入$d$
则$f[6][3][2]$会转移到$f[7][4][3]$去
但$f[7][4][3]$这个状态根本就是非法的

于是为了解决这个问题,我们不得不预处理出那些状态/转移是合法的
但我们发现这样的话,一般的预处理必须依赖文本串长成啥样,但这样做是爆炸的
于是考虑一个新的定义:$f[i][a_1][a_2]\ldots[a_n]$ 表示文本串到第$i$位时,文本串匹配到第$j$位,LIS的长度为$a_j$的方案数
这样的话,如果我们始终保持进行最优的转移,就不需要记录文本串的状态了
另外,我们还可以优化,因为$f[i][j] \le f[i][j+1] \le f[i][j]+1$,于是我们可以打成差分,然后压成二进制状态$S$
于是我们的状态就变成了$f[i][S]$,再预处理出转移数组 $trans[S][C]$ 表示状态为$S$,加入字符$C$之后应该到的状态
于是进行类似的转移就可以啦:$f[i+1][trans[S][C]] = f[i+1][trans[S][C]] + f[i][S]$

12 thoughts to “【BZOJ 3864】Hero meet devil”

  1. You have observed very interesting details! ps decent web site. “I just wish we knew a little less about his urethra and a little more about his arms sales to Iran.” by Andrew A. Rooney.

  2. 75271 610552We are a group of volunteers and opening a new scheme in our community. Your internet internet site given us with valuable details to work on. Youve done an impressive job and our entire community is going to be grateful to you. 228261

  3. 430466 914023Average In turn sends provides could be the frequent systems that supply the opportunity for ones how does a person pick-up biological, overdue drivers, what one mechanically increases the business. Search Engine Marketing 835489

  4. 682913 772357When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is added I get several e-mails with the same comment. Is there any way you can remove me from that service? Thanks a lot! 982341

  5. I’ve been exploring for a little bit for any high quality articles or blog posts on this sort of space . Exploring in Yahoo I eventually stumbled upon this website. Studying this information So i’m satisfied to exhibit that I have a very good uncanny feeling I discovered just what I needed. I such a lot certainly will make sure to don’t forget this web site and give it a glance regularly.

Leave a Reply

Your email address will not be published. Required fields are marked *