URAL 1158 — Censored!
一个晚上,在Nxun和MaShuo的帮助下,终于AC了URAL的1158…
这道题是一个自动机上的DP,算是挺经典的了.
首先按照那些forbidden words建立自动机,并在适当的位置标注该位置是某个单词的结尾.然后,f[i, j]表示当前在自动机上走第i步,走到了Trie树的第j号结点.则f[i, j] -> f[i+1, pre]; f[i+1, k]; 0.其中,pre代表在自动机上不断找pre找到的那个结点…不太好表述,就是说在下面没有孩子结点的时候不是向上走么…然后就是最后走到的那个结点…f[i+1, k]是正常情况,就是k是j的孩子结点,然后就f[i+1, k] <- f[i+1, k] + f[i, j].0是说,对于上面的那个f[i+1, k],若k是一个单词的结束,那么肯定不能到k啊…所以f[i+1, k] <- 0.
发现自动机上的DP还挺难表述…
不过要注意一点的是,比如i结点是j结点的pre,那么如果i是一个单词的结束被打上标记,j也要被打上标记(就是我在程序里用//important!注释标注的那一句).刚开始的WA就是这个原因.
这道题的提交结果:WA on Test 2; WA on Test 13; AC.第一次的WA很无语…BFS和跑自动机写到了一起…转移方程不对…还好挺好改.
{ URAL 1158; Censored! - sqybi’s code - 自动机+DP}//for my winsty{$APPTYPE CONSOLE}program ural1158_sqybi; const nn = 50; mm = 50; pp = 10; rr = 10; […]