1. 题目

传送门= ̄ω ̄=

2. 题解

[2017年5月16日]
听说能用trie树做。
记忆化非递归式深搜。
设$book(i)$表示状态$i$是否达到过(即前$i$个字符都成功分解)。
枚举子串即可。

(在这份代码下面有更优做法!)

代码:


[2017年5月26日更新]
额,昨天试着把上面的代码交到codevs上结果RE
经过检查,发现是递归爆栈了。
于是开始写递推做法,不用dfs。。。
加了个优化,就是把子串按照长度从小到大排序,如果排前面的因过长而不符合条件,那么后面的也都不符合了。
这样以来最慢的点是5ms(codevs,luogu最慢是4ms),比trie树还快(dalao们说trie树49ms)。
代码也短= ̄ω ̄=

代码: