HDU 1560 - DNA sequence
Problem : Given a list of strings (N<=8, len<=5), find the shortest string s.t. each string in the list must be the subsequence of the answer.
Solution : f[a1][a2]...[an] is the shortest string which has subsequence of s1[1..a1], s2[1..a2], ..., sn[1..an]. Thus f[a1][a2]...[an]=min{f[a1]...[ai-1]..[an]+1 | where all the si[ai] has the same element }. Since all the element of f comes a previous status plus 1, thus bfs can solve the problem.
Note : Since the number of status is very big (O((len+1)^N)), and the number of test cases is also very big, do not use memset to clear the status. (Get TLE for multiple times here)