[Shoi2013]阶乘字符串
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
----------------------------------------------
比较神奇的DP
f(i)，i是前n个字符的集合，表示这几个字符的全排列出现的最早位置，没有出现设为+∞
转移:f(i)=max{next(f(i-c),c)}
c∈i
i-c表示去掉c这个元素
next(a,b)表示a这个位置，b下一次出现的位置，可以预处理出来
这个DP相当于枚举一个集合，然后枚举最后一个字符，然后看一下去掉最后一个字符之后的全排列最晚的位置，然后再加上这个字符
枚举一遍集合中所有元素作为最后一个字符，一定枚举到了所有情况
----------------------------------------------
评论 (0)
