HBC230858[HAOI2008]玩具取名,区间dp,动态规划Encoded Strings II题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

Tommy has just invented an interesting string encoding algorithm, which is described below. For every string SSS, we may define a character-mapping function FSF_SFS​, which maps every character occurring in SSS to a lowercase letter, as below FS(c)=chr⁡(G(c,S))F_S(c) = operatorname{chr}(G(c, S))FS​(c)=chr(G(c,S)) where chr⁡(i)operatorname{chr}(i)chr(i) is the (i+1)(i+1)(i+1)-th lowercase Latin letter, and G(c,S)G(c, S)G(c,S) is the number of different characters after the last occurrence of ccc in SSS. To encode a string SSS by Tommy's algorithm, replace every character ccc in SSS by FS(c)F_S(c)FS​(c) simultaneously. For example, the encoded string of "abc" is "cba", and the encoded string of "cac" is "aba". You are given a string of length nnn and then encode all the 2n−12^n-12n−1 nonempty subsequences. Your task is to find the encoded string that has the greatest lexicographical order among all the encoded strings.

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC230858[HAOI2008]玩具取名 区间dp 动态规划Encoded Strings II题解