[LA3942]Remember the Word

请容许我爆粗口……

调个bug调了30分钟……

结果是不能每组数据重新开Trie!!!

题目(vjudge)

首先要明白这题是dp,

用dp[i]表示从i开始的字符串有多少种分解方法,

转移方程很简单,dp[i]+=dp[i+strlen(x)] | x串为当前串的前缀。

但是我们不会去枚举每个x串,否则时间爆炸。

解决方法就是将所有x串加到一棵Trie里面,

然后用i串去查找,只要到了某个节点上有x串,就执行转移方程。

完毕。

 

发表评论